Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning
Authors: HYUNWOOK KANG
Taehwan Kwon
Jinkyoo Park
James R. Morrison
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-agent assignment planning
Reinforcement learning
Graph neural network
Mean-field inference

Abstract: This paper explores the possibility of near-optimally solving multi-agent, multi-task NP-hard planning problems with time-dependent rewards using a learning-based algorithm. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problems well model ride-sharing, pickup-and-delivery, and a variety of related problems. In representing the MRRC problem as a sequential decision-making problem, we observe that each state can be represented as an extension of probabilistic graphical models (PGMs), which we refer to as random PGMs. We then develop a mean-field inference method for random PGMs. We then propose (1) an order-transferable Q-function estimator and (2) an order-transferability-enabled auction to select a joint assignment in polynomial-time. These result in a reinforcement learning framework with at least $1-1/e$ optimality. Experimental results on solving MRRC problems highlight the near-optimality and transferability of the proposed methods. We also consider identical parallel machine scheduling problems (IPMS) and minimax multiple traveling salesman problems (minimax-mTSP).

Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning
Hyunwook Kang* Department of Computer Science
Taehwan Kwon
Kakao Brain
Texas A&M University
isaac. kakaobrain.com
hwkang@tamu. edu
Jinkyoo Park
James R. Morrison Electrical Engincering
Industrial & Systems Engineering KAIST jinkyoo.park @ kaist.ac.kr
Central Michigan University morri I @ emich.edu
Abstract
This paper explores the possibility of pear-optimally solving aulti-agent, multi-task NP-hard planning problems with time-dependent rewards using a learning baased algorithm. In particular, we consider class robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problems well model ride-sharing, pickup-and-de and-deliveryy and variety of related problems. In representing the MRRC problem as a sequential decision-makinn problem, we observe that each state can be represented as an extension probabilistic graphical models (PGMs), which we refer to random PGMs. We then develop mean-field inference method for random PGMs. We then propose (1) an order-transferable Q-function estimator and (2) an order-transferabiiit-eeee
auction to select a These result a reinforcement learning
joint assignment in polynomial framework with at least - 1/e optimality. Experimental results solving MRRC problems highlight the near-optimality and transferability of the proposed methods. We also consider identical parallel machine scheduling problems (IPMS) and minimax multiple traveling salesman problems (minimax-mTSSP)
Introduction
Motivation Consider set of identical robots seeking to serve set of spatially distributed tasks. Each task given an initial age (which then increases linearly time). Greater rewards are given to younger tasks when service is complete according to predetermined reward rule. Such problems prevail in operations research, e.g., dispatching drivers to transport customers or scheduling machines in factory. Solving such highly structured NP-hard problems with the constraint of "no possibility of two robots assigned to one task at once' using mathematical optimization schemes is infeasible or ineffective due to the expensive computational cost, especially when the problem size is large. Applying dccentralized approach using multi-agen, modeling frameworkLong et al. (2020); Rashid et al. (2018); Sunchag et al. (2017) is possible way to solve large scale problems. However, due to the impossibility of inducing consensus among agents in achieving the global objective without
* First author
corresponnence to: Jinkyoo Park (jinkyoo.park @ kcist.ac.kr), James R. Morrison (morri Ij @@cmich.edu)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

effective communication Fischer et al. (1985), such decentralized approaches are rarely used in industries (e.g., factories). Thus, this study focuses on centralized methods for solving MRRC.
Research Questions. Many of such NP-hard scheduling problems have time-dependent rewards. To the best of our knowledge, these problems have not yet been addressed by non-decentralized learning-based methods. Even if one can, it must also be able to simultaneously address a fundamental challenge: the number of possible robot-task pairs be considered increases exponentially. For instance, scheduling 8 robots and 50 tasks involves 10t8 possible joint assignments at each time-step. The main research question that the current study seeks to resolve "how to design computationally effective (i.e., scalability in terms of learning and decision making) a learning based centralized decision making scheme for solving large-scale NP-hard scheduling problems?"
Proposed method and contributions. The present paper explores the possibility of near-optimally solving multi-robot, multi-task NP-hard scheduling problems with time-dependent rewards using bearning-based algorithm. The study formulates multi-robot, multi-task NP-hard scheduling problems in sequential decision-makinn maninn framework and derives a joint scheduling policy with a theoretical performance bound under reasonable assumptions. The novelties of the current study are as follows:
The study first observes that a state-joint assignment pair can be represented as a random PGM. After developing a theory of random PGM-based mean-field inference, we derive random struc- ture2vec, a random PGM-based extension of structure2ved Dai et al. (2016).
We estimate the Q-function (skk, as.) using layers of random structure2vec, where (sk, (x. is the state-joint action pair. Using an interpretation of a layer of structure2vec as a Weisfeiler- Lehman kernel (as in Dai al. (016)), we design the estimator to possess property we call order-transferability This property enables transferability in problem size.
We propose a joint assignment rule called order- taaeertttanffablltt---neee enabled auction policy (OTAP) to address exponential growth in joint assignment space. We propose auction-fitted Q-iteration (AFQI) by substitution of the argmax operation of fitted Q-iteration with OTAP to train the Q-function in scalable manner. We prove that AFQI results in policy with polynomial-time computation that achieves at least 1 1/e performance compared with the optimal policy.
Results and Impacts. Using simulation experiments, we show that the proposed policy typically achieves 97% optimality for the multi-robot reward collection (MRRC) problem in a deterministic environment with linearly time-varying rewards. This performance is well extended experiments with stochastic traveling times. To the best of our knowledge, this result is the first to learn a near-optimal NP-hard nulti-rrooo/maachne scheduling policy with time-dependent rewards.
Related studies.
Reinforcement Learning based Vehicle Routing Problems. Mazyavkina et al. (2020) have catego-
rized the RL approaches solving vehicle routing problems into two: (1) the improvement heuristics that learn an operator can iteratively improve the entire routing plans until there is no improvement is
made (Wu et al. 2020 da Costa al., 2020 Chen Tian 2019 Lu et al. 2020 Kim al. 2021). (2)
the construction heuristics that leamn a policy that sequentially make single routing action given the partial solution (state) (Bello et al. 2016; Nazari al.) 2018 Kool al. 2018 Khalil al., 2017).
and (3) the hybrid approaches that mix these two approaches (Joshi et al. 2020; Fu et al. [022]] Kool et al. 2021 Ahn et al.) 2020). These RL approaches have mainly considered a single-agent routing problem. Although these methods solve CVRP with multiple vehicles, they solve this problem from a single-agent perspective. In addition, most of these approaches consider the static reward function setting. On the contrary, our study explicitly considers multi-vchicle interaction while considering the time-varying reward, which is a more realistic routing problem setting.
Graph Inference Based Approach. Dai et al. (2017) showed that a graph neural network (GNN) called structure2vee Dai et al. (2016) can construct solution for the Traveling Salesman Problem (TSP). structure2vec is popular GNN derived from mean-field field inference with a probabilistic graphical model (PGM). Dai et al. 2017) formulates the TSP as a Markov decision process (MDP) where a heuristically constructed PGM represents each state-next assignment pair. They employ structure2vec derived from the heuristic PGM to infer the Q-function, which they use to select the next assignment. While their choice of PGM was heuristic, their approach achieved near-optimality

---

(sk = (ge. Dz).
(((x))IEX,))
(Pd
4g
R
Es
random PGM
random struct2vvc
La
(H (K))
RTT
P = 1) = Ppg
Scenario: (ry: E -> Egr rgl Eo - E2 ts)
Figure 1: Representation of the scheduling problem using random PGM
and transfcrability of their trained single-robot scheduling algorithm to new single-robot scheduling problems with an unseen number tasks.
3 Multi-Robot Reward Collection Problem
In the main text, we model a general multi robot/machine scheduling problem as a discrete-time, discrete-state (DTDS) sequential Decision-making problem. In the DTDS model, time advances in fixed increments A, i.e., f = to + A where t4 is the actual time after decision epochs have passed. For simplicity, this framework, 8ı denotes a state, and action dg denotes a joint assignment of robots/machines to unfinished tasks the kth epoch. The objective of the problem is learn the optimum scheduling policy To 8 + Gg that maximizes the reward collected or minimizes the total completion time (a.k.a. makespan minimization). Below is the formulation of MRRC. We additionally propose continuous-ting time continuous-state (CTCS) problem to identical parallel machine scheduling problems (IPMS) Appendix A and minimax multiple traveling salesman problems Eminimax-mTSS in Appendix B
use & time index representing the kth decision epoch. In
3.1 State
The state at epoch is represented as (gk, D&) where a graph 9b = ((R, Tx), (ETT, ,ERT) and associated feature set D (D DJ DJT DRTT.. The elements of graph IN are defined as (See Figure l):
R = [I, M) } is the index of all robots. The index i and will be used to specifically denote robots.
To = [1...., N} is the index set of all remaining unserved tasks at decision epoch k. The index and q will be used specifically denote tasks.
= ( pp E Tk, g Th) is the of all directed edges from a task in Ta. any task in Tu- We consider each edge
random variable. The task-to-task edge TT indicates the event that robot that has just completed task subsequently completes task We denote the probability p(e
TT = =) E [0, 1] the presence probability of the edge TT. Epq
ERT = (c (CRTiE E is the set of all directed edges from robot in R to task in Tk- We say the robot-to-task edge RT
indicates the event that robot i assigned to the task p. This edge is defined deterministically depending the joint assignment action. If robot is assigned to task p. then p(c RT = 1, otherwise
The element of feature set Dj associated with the graph 9 is defined as:
DjR {d i E RJ is the set of node features for the robot nodes in R at epoch k. In MRRC, dft is defined as the location of robot at epoch & (epoch index is omitted).
DJ = [d]] Ip E Tx is the set of node features for the task nodes in Ts epoch k. MRRC, oz is defined the age of task p at epoch & (epoch index & is omitted).

---

TT.q ] is the set of task-task edge features at epoch k. d denotes the duration for a robot that has just completed task p to subsequently compete task q. We call this duration task completion time. In MRRC, task completion time is given as random variable (in practice, our method only requires a of samples of random variable).
D {d E R. p E T& the set of robot-task edge features at epoch k. d denotes the traveling time for robot to reach task p.
3.2 Action
An action Og. a joint assignment at epoch k, is defined as a maximal bipartite matching of the complete bipartite graph (R, Tk. & R composed of the robot nodes R, the remaining task nodes Te. and the fully connected edges between them ERT, That is, given the current state šą (gk. Dx), og is a subset of E satisfying (1) two robots can be assigned to the same tasks, and (ii) robot may only remain without assignment when the number of robots exceeds the number of remaining tasks. If 2 E ak. it means that robot is assigned with task at epoch k. For example, Figure shows the case where as ( RT) (Note, we equivalently may say this as 61,1 T and otherwise.) In MRRC, all robots are allowed to change their assignments at each decision epoch. (In
IPMS and mTSP, only free machines/salssmen are newly assigned.)
3.3 State transition
As the joint assignment aş is executed given the current state Ss. (gk. Dx) the next state 8x41 = (gh+1, Dx+1) ) is determined with the updated graph J++1 and features Dx+1-
Graph update. When the decision epoch corresponds to the point when task is completed, the corresponding task node will be removed in the updated task nodes as Tk+1 Tx/ [p), and the task-task edges and robot-task edges, E and RRT
will be accordingly updated.
*++1'
Feature update. At decision epoch ls + 1, DR+1 (D DT k+1 K+1. DRT) is determined. In MRRC, task locations D {df R} and task ages D k+1 {dl Ip Tk+1) updated. The robot-task edge features DRT will be updated according D as well.
3.4 Reward and objective
At time 0, each task is given initial age which increases linearly in time. A reward rı (dl is given when a task p E Tk, whose age dg is served epoch k. We consider linear and nonlinear reward functions r for MRRC. The objective is to learn a stationary policy function that maps current state s into current action a, to maximize expected total collected rewards (*(ssa) =: E K=
Ep,x
R(Sty 0t2: St241 ( |[6
s, 0t = a].
4 Random graph embedding: RandStructure2Vee
We observe that when task completion time is not deterministic, a scheduling problem can be represented as an extension of probabilistic graphical models (PGMs), which we refer to as random PGMs. This section proposes mean-field inference method, random struct2vec, for random PGMs to estimate the state-action value Q(sk, ax) in solving MRRC.
4.1 Random PGM for representing a state of MRRC
factor the joint distribution p (X) as p ( II, di (D:) where (D,)) denotes marginal distribution or conditional distribution as- sociated with a set of random variables D.; is a normalizing constant. Then {X,} } is called a probabilistic graphical model (PGM). In PGM, D; is called clique and (D. is called the clique potential for D,, and D, is called the scope of o;. We often write simply d,, suppressing D,.
Given random variables X {Xp}. suppose that
Starting from a state and action ag, one can conduct random experiment of "sequential decision making using policy n". this random experiment, we can denote the events 'How robots serve all remaining tasks in which sequence' as scenarios. For example, suppose that at time-step & we

---

are given robots {ri. r2), tasks {tz, t2, t3, ta. ts. ts. and we follow the policy x onward. One possible scenario that robot ri serves tasks {t, > t4} and robot r2 serves tasks {tz - t2 + is + t&} (see Figure 1). Note that the time when 1s is served depends on the time when 12 is served (state transition is Markovian); thus the reward from 4s depends on the reward from l2. shown in Figure 1. (,((1 + ), {43 - 12 + is - (t3) can be represented as a single instance of Bayesian Network. Since scenario realization is random, we can construct the distribution over such scenarios using 'random' Bayesian Network with random node X (sp, as)) and clique potential ø. For details, see section
4.2 Mean-field inference with random PGM
Let x= [Xpp be the set of all random variables in the inference problem. Let 9x be the set of all possible PGMs X' Let P Gx [0, 1] be a probability measure Gx. Define random PGM on X' as {Gx, P). Note that the inference of {9x. P} will be difficult; |gx] is too large for inferring P even using Monte-Carlo sampling approach. To avoid this difficulty, we use the approximated inference using semi-cliques. Suppose that we are given the set of all possible cliques on X' as Cx. As PGM will be realized according to P, only few of the possible cliques in Cx will be actually realized as an element of the PGM and become real cliques. We call such potential clique elements of Cx as semi-cliques. Note that if we were given P. we could calculate the presence probability pm of the semi-clique Dm as Pm = EGeex P(G)1D,,.G. EG, where 1 denotes the indicator function.
Mean-field inference with random PGM. We start from a specific inference problem and state the main theorem in more general way. Consider a random PGM on = ({ }. {X₂3) where Hş is the latent variable corresponding to the observed variable X₁. Our goal is to infer {H given (X,) by finding p(1 H. Ka, F). mean-field inference, we instead find a set of surrogate distributions (g(x,) (H.) for which {H&} are independent. Here g( means that q is a function of (2y)).
We next state Theorem I. in very general manner. The statement is the same as that of mean-field field inference with PGM Koller & Friedman (2009) except that ours has the presence probability terms
} of semi-cliques {Pm]. The implication is that inference of presence probability of each semi-clique enough to conduct mean-fiele inference, and the inference of (9x,P) is not needed.
Theorem Random PGM based mean field inference. Suppose a random PGM on X = (Xp)
given, and the presence probability {pm} for all semi-cliques Dm E Ex are known. Then, the surrogate distribution (4p(xp)) in mean-field inference is optimal only if Up (xp)
P.mx,,DD,,,PBBeeee Z, exp {EmXXED Pm (Xx)) [n om (Dm:Ip)) where Zp is normalizer and om clique potential for Dm-
For the general background and proof, see Appendix C
RandStructureeVee. In Dai et al. 2016). structure2vee was derived as a vector space embedding of mean-field inference with PGM. For detailed background on vector space embedding, see Appendix D From Theorem 1, we derive random structure2vec as vector-space embedding of mean-field inference with random PGM. Suppose that once a PGM realized the PGM has joint distribution proportional to some factorization II, (Hp!?p) Ip.. & (Hpl Hg) (as in Dai et al. (2016)). Under this assumption, we can write (HH5))(H,)) as (Ha In Dai et al. (2016). they suggest that 1xtp structure2vec is essentially fixed point iteration jip < oWW1x + W2 Egzp Mg)) where ü is latent vector for node and 4p is input for node p. They show that, when we interpret ji; as a vector space injective embedding expressed as fı; = SN ( for some ó, structure2vec's fixed point iteration is the embedding of fixed point iteration of mean-field inference with the PGM. Lemma I states that we have a similar result for random PGM by including only the {pop) information.
Lemma 1. Structure2vec for random PGM. Assume that the presence probabilities {ppp) for all pairwise semi-cliques Dap E Ex are given. Then embedding the fixed point equation Theorem I generates the fixed point equation Ph t a (Waap- + W2 Eqep Puplia. We refer to this fixed point iteration random structure2vec. (The proof of Lemma I can be found in Appendix E
5

---

Remarks, Note that inference of (9x. P) is in general a difficult task. One implication of Theorem I that we transformed a difficult inference task into a simple inference task: inferring the presence probability of each semi-clique. (See Appendix F for the algorithm that conducts this task.) In addition, Lemma / provides theoretical justification ignore the inter-dependencies among edge presences when embedding random graph using GNN. When graph edges are not explicitly given or known to be random, the simplest heuristic one can use is to separately infer the presence probabilities of all edges and adjust the weights of GNN's message propagation. According to Lemma 1, possible inter-dependencies among edges would not affect the quality of such heuristic inference.
Solving MRRC with RandStructure22ee
Multi Robot Rewward Callection (MRRC)
Action Value inference
Sequential Graph Imbedding
Aust on based Secetion
Grapph State Seproueciation
Daterce Emitedding Value Embeddin
D Edtimatio
Q of)
Agent
Environment
Auction
Tasks
mardo
Todel
---4- QG.4f)
Agent 2
Task with
BDT)
Currene age
ct
Tacke
otr..
Age zt complesion Exporentially decaying ROWA
Dan
Reward Tr
Auction Fiteed O terzton Optimie Medel Farometer:
Figure 2: State representation and main inference procedure
This section describes how the proposed method solves the MRRC problem with the newly developed
random structure2vee method. The total solution (i.e., the sequential assignments of robots/machines to tasks) is found by iteratively repeating sequential decision making. This section specifically describes how to choose a joint assignment d given the current state 8 = (gk. Dz). The procedure for determining a joint assignment action is composed of (1) represent the state using random Bayesian Network, (2) estimate the Q-value using random graph embedding, and (3) select a joint assignment. Figure 2 depicts the overall procedure. This section focuses on MRRC; the appendices will provide the formulation, solution procedure, and results for IPMS and mTSP problems as well.
5.1 Representing state using a random PGM
In this section, we describe how the MRRC problem state and one possible joint assignment ag can be represented as a Bayesian network. Assume Hş. the hidden random variable for task carries information about the benefit of serving task p. Given a scenario (see section 3.1), Hp depends on H, only if q is served after p by the same robot, and H, depends on Xp, the observed features for task p. For an MRRC problem, X, can be either a task's assignment information aRT or a task's age d.. Based on these definitions, a Bayesian Network for {Hp} and {Xp} as p( (Hp)) = II & (Hp)x)) Ip @ (Hp)Hg) This Bayesian Network corresponds to one scenario; there are many possible scenarios that can be realized randomly. Since random PGM natu- rally models this characteristic, according to Lemma 1, are justified to random structure2vec with edge (semi-clique) presence probabilities (p(eTT) from in section 2.1.
} is constructed
5.2 Estimating state-action value using Order trainability-enablled Q-function
We illustrate how we can estimate a Q-function for MRRC by applying random structure2vec to the random PGM that represents as), Lemma provides the fixed point equation Po
Wiæp W2 Ejet Paplig to compute the embeddings OS for node task p in a random PGM. The embeddings üo for p E are computed in an iterative manner using random structure2vec as:

---

(r+1)) = (W1xp+ + W2 CatpPopfhy" We propose a network architecture composed of two-step Pp
sequential random structure2vec, which is composed of action embedding and value embedding.
Action Embedding. The first random structure2vec layer emheds the joint assignment into the task nodes Ty = [1.... The action embedding ūn for task node is defined as the fixed point for the equation F2 a (W11z) W. E Copp Paplin) where zi d.pT (distance from robot to task p) when task p is assigned to robot i, x O when task p is not assigned. The action node embeddings {ūAl / E }. computed via iteration simultaneously by employing random structure2vec, provide sufficient information about the relative locations between robots and their assigned tasks.
Value Embedding. The second random structure2vec layer embeds the task ages into the task nodes. The value embedding P for task node p is defined as the fixed point for the equation Fh a (W.y' m. + +W''' Enpp Paplly) where zy -ip d,) is the concatenation of the action embedding jng computed by the first layer and the task age d7, for node p. The resulting value node embeddings {Mip] Ip E } computed in an iterative manner, provide sufficient information about how much value is likely in the local graph around each task by the specified joint assignment.
Computing (s( ax). To derive (sk, ag), aggregate the embedding vectors for all nodes by uu = Ep Ph to obtain one global vector j to embed the value affinity of the global graph. We then use neural network map j into Qo(sk, ax). The overall pseudo-code for estimating steps is provided in Appendix G
It is essential for the proposed inference method can estimate the state action value Qs(sk, as) for varying graph size gt. Let us provide the intuition related to scuh problem-size transferability. For Action Embedding, transferability is trivial; the inference problem is a scale-free task locally around each node. For Value Embedding, consider the ratio of robots to tasks. The overall value affinity embedding will be underestimated if this ratio in the training environment is smaller than this ratio in the testing environment; overestimated overall otherwise. The intuition is that this over/under-estimatton
does not matter in Q-function based policies discussed in van Hasselt et al.) (2015) as long as the order of Q-function value among actions are the same. That is, as long as the best assignments chosen the same, i.e., arg maxa, (skk ax) = arg maxa, Qo(sk, a& the magnitude of imprecision Q(sk, ax)) Qe 0x)l does not matter. We call this property of an estimator tadf--rranfferabiliiy (with respect to the max operation).
5.3 Selecting joint assignment using OTAP
With the previously introduced way to estimate Qa(sk, ax), we illustrate how to compute the joint assignment (action) oj. a maximal bipartite matching in the bipartite graph (R, TT,&KK ERT), given the state 8 (yk, DR). Specifically, we propose the order transferability-nnabe
auction policy (OTAP) that constructs a joint assignment ag through N max (| [k]) iterations of Bidding and Consensus phases. This auction follows the spirit of Sequential Single Item (SSI) auctioning (Koenig ct al. (206))); each iteration adds one robot-task assignment to construct a full joint assignment.
Bidding-phase. In the th iteration of the bidding phase, given M¹ (111), the ordered set of n 1 robot-task edges in & determined by the previous n - iterations, all the unassigned robots bid their the most preferable task to conduct. Respecting robot-task assignments determined in previous n 1 iterations and ignoring other unassigned robots, each unassigned robot i select the best task assignment e that maximizes (sk, M U [< (TT)) among all unassigned tasks p E Tk. where Q3 is the 0-parameterized network with superscript n indicating that the state action value is estimated at th iteration. Then, robot bids {e/eT, (5k, M Mf--1) U (E RT }}} the auctioneer.
This bidding occurs simultaneously by all the unassigned robots the nh iteration. Since the number of ignored robots varies at each iteration, transfcrability of Q-function inference is crucial.
Consensus-phase. In the consensus phase of th iteration, the centralized auctioneer finds the bid with the best bid value, say {< RT p' Q7 M (nn UETT }}} (Here i" and p² denote the best robot
task pair.) Denote RT := (n) The auctioneer sets everyone's MM( as M! = =M M U mg and initiate bidding phase for the remaining unassigned robots.
7

---

These two phases iterate until reaching M joint assignment a of N N-robots at time step k. That is, ( az. The computational complexity
{mg ,...; 1 (N)
(1)
This M,
(N) is chosen as the
for computing Te is O (IR) [T]) and is only polynomial; see Appendix L
5.4 Training Q-function using AFQI
The fitted Q-iteration (FQI) finds that minimizes Es (e.. 1DD [Qa ($k, (3)) [r (sks as) + y max, Qo (88+1, a)]] where D denotes the distribution of training data. We propose a new rein- forcement learning method, which we call Auction-fitted Q-iteration (AFQI), which replaces maxe Qo (sk, a) used in the conventional FQI with OTAP. That is, writing OTAP as TQ.. AFQI finds 0 that
empirically minimizes (E QQ (8k: (x) - [r (82. + QQ (#++1; (#k+1))]]-
In learning the parameters A for Qa ($k, ax), we use the exploration strategy that perturbs the parameters 0 randomly to actively explore the joint assignment space with OTAP. While this method based methods Plappert et al. (017), exploration in
was originally developed for policy-gradien parameter space is useful in our auction-fitted Q-iteration since generates reasonable combination of assignments.
Theoretical analysis
We show the proposed AFQI obtains at least - 1/ee optimality and enables computation of the joint assignment in polynomial time. This result is achieved by the order-transferabiiity of the proposed Q-function estimator and its use in selecting the joint assignment.
6.1 Performance bound of OTAP
Recall that Q" denotes the n-robot problem's true Q-function. In the same way defined M, (N) above, denote the joint assignment chosen by OTAP as {Q") as M(N) {m()) (N)
Lemma 2. If the Q-function approximator has order transferabilityy, then M(N) (
For any decision epoch let M denote a set of robot-task pairs subset of T. For any robot- task pair m E ERT define A (m .M) : QIMU(m)) Mu [m]) (sM, as the the marginal value (under the true f-funciions) of adding robot-task pair m E & Lemma 2 enables us to use the result discussed in Nemmauuser et al. (1978) and achieve the result of Theorem 2.
Theorem 2. Suppose that the Q-fanction approximation with the parameter value 0 exhibits order
transferability. Denote ( as the result of OTAP using {Q%) and let M argmax Qlau (sk: az). If (m MM 2 0, V. C E Vm E ERT, and the marginal value of adding one robot diminishes as the number of robots increases, i.e., A(m [M) < Am [N,, VN C C E Wm E &RT, then the result of OTAP is at least better than - l/e of an optimal assignment. That is,
QN (sk, MM (( (sk,,
(sk, M1 1/e). See Appendix and K for the proofs.
6.2 Performance bound of AFQI
AFQI seeks to find 0 that minimizes E 11)~11 IQa (Sk. ax) - |r (sk. 0x) + 7Qp (8K+1, TQ, (+k+1))]]- Here, we use OTAP, denoted as TQ.. instead of max, Qo (Sk, a) which is used in general fitted-Q iteration. As we have seen section 5.1, OTAP replaces the max operation with the auction algorithm with provable performance bound compared with the max operation. Lemma 3 allows us to use this performance bound obtain a performance assurance on AFQI compared with FQI. We only write an abbreviated version of the statement for brevity. The formal description of conditions and the proof is provided in Appendix
Lemma 3. Kang & Kumar (2027) Suppose that 1 1/r approximation algorithm is substituted for the max operation in FQI. Then, the corresponding new Fitted Q-iteration's performance is least
1 - 1/r optimal.
Corollary 1. AFQI achieves at least 1 1/e performance compared with the optimal policy.

---

Table 1: Performance test (50 trials of training for each case)
Testing size
Rohot (R)
TTask (T)
Reward
Environment
Baseline
2R/20T
3R/20T
3R/30T
5R/30T
5R/40T
8R40T
8R/50T
Optimal
98.31
97.50
97.80
95.35
96.99
96.11
96.85
(+1.23)
(#1.71)
(45
(#5.28)
(#5.42)
(=1.50)
(=3. 10)
Deterministic
Ekisi al.
99.86
97,50
118.33
110.42
105.14
104.63
120.16
Lineur
(13.24)
(122665)
(12.84)
(12.97)
(13.78)
(22.50)
(23,94)
1373
120.6
129.7
T10.4
1230
119.9
T19.8
(1.5.65)
(d:5.03)
(455554
(44.34)
(244977
(:4.74)
(25.84)
Stochastic
SGA
(+:4.02)
130.9
(#4.003
115.7
(#5.21)
122.8
(#6.23)
115.6
(#4.94)
122.3
(=5.63)
113.3
(=4.08)
115.9
Deterministic
SGA
111.5
118.1
118.0
110.9
118.7
111.2
112.6
(#:3.71)
(#5.56)
(#5.09)
(#44664
(#5.23)
(=5.38)
(=5.07)
Nonlinear
110.8
117.4
119.7
111.9
120.0
110.4
112,4
Stochastic
SGA
(45.17)
(46.22)
(44.44)
(44.70)
(#6.38)
(#5.14)
(=5.30)
Table 2: Transferability test (linear & deterministic env, standard dev. provided in the appendix)
Training
Testing size: Robot (R) / /Task (T)
#RV
2R/20T
3R/20T
3R/30T
5R/30T
SR/40T
SR/40T
8R/S0T
2R/20T
98.31 (#:4.23)
93.61(:b4.98)
97.31 (d:4.25)
12.16.33.400
92.83(1:4225)
90.94(+:3.98)
93.44 (2-4.22
3R/20T
95.98(+)1.75)
97.50X 71))
96.11
93.6K(+-1.51))
91.75(#5.71)
91.60(=5.03)
92.77(++1.44)
3R/30T
94, (4(:9777))77
(6.177))2.22))
97.80 14)
94.7%(+3.55)
(8)78))7778)
93.14(=+4.50)
93.28(++3999)
SR/3UT
97,83(+:311))
94.89(:t:4443)
96.43((+-4.233
95.35 28))
43.28(:+4.18)
92.63(++5007)
92.40((=4.10)
SR/40T
97.39(1).665)
94.69(1):.01)
95.22((14.888)
93.15(155009)
96.99 4..42)
94.96((13394
93.65 (1:5.66)
8R/40T
95.44(#4.322)
94,43( 88)
93.48(+4.337)
93.93(+55055
96.41(+3.96)
96. 06.11+44.00
95.24(#44444)
SR/50T
95.69(#:3118)
97.35(+-4.20)
94.02(+:2.69)
94.50:::4.444
94.86(1:3.26)
96.85:133400
Table 3: Training complexity (mean of 20 trials of training, linear & deterministic env.)
Testing size : Robot (R)
Task (T) SR/UUT
Linear & Deterministic
2R/2UT
3R/20T
3R/30T
SR/30T
SR/4TT
SR/50T
Performance with full training
98.31
97.50
97.80
95.35
96.99
96.11
96.85
Training optimality
19261.2
61034.0
99032.7
48675.3
48217.5
45360.0
47244.2
6.3 Experiment settings
In the main text, we focus on discrete-time & discrete-state (DTDS) MRRC problems with deter- ministic and stochastic task completion times. For CTCS deterministic problems with real-world datasets, see IPMS (Appendix and mTSP (Appendix B
Environment. Since there is no standard dataset for MRRC problems, we used the complex maze-like environment generator of Neller et al.] (2010) (code provided in Appendix 10). This complex maze mimics the complex road layout of city and random traffic, inducing nontrivial task completion times. See the leftmost image of Figure and the supplementary video. We randomly generated a new maze for every training and testing experiment with randomly chosen initial task/robot locations. To generate the task completion times, Dijkstra's 's algorithm and dynamic programming were used for deterministic and stochastic environments, respectively.
In the stochastic environment, a robot makes its intended move with a certain probability. (Cells with dot: success with 55%, every other direction with 15% each. Cells without a dot: 70% and 10%, respectively.) A task is considered served when a robot reaches it. We consider two reward rules: linearly decaying rewards f(age) max/200 age, 0} and nonlinearly decaying rewards f fage) = X age with À = 0.99, where age is the task age when served. The initial age of tasks are uniformly distributed in the interval [0, 100).
Baselines. For deterministic environments with linear rewards, where the corresponding MRRC can be formulated as mixed-integer linear program (MILP), we consider the following two baselines: Optimal: Gurobi Gurobi Optimization (2019), off-the-self the optimization solver for MILP, was used to solve the problems with 60-min time limit.
Ekici et al.: Ekici & Retharekar (2013), the most up-to-date heuristic for solving MRRC in the Operations Research community, was used the problems.

---

For stochastic environments exponential rewards, to our knowledge, there is no literature addressing MRRC with. Thus, we construct an indirect baseline:
* Sequential Greedy Algorithm (SGA): general-purpont multi-robot task allocation algorithm
called SGA Hin Choi et al. 20099.
The performance measure we used is Rewards cullected by the proposed method Thus, the value of
Reward collected by the haseline
greater than 100% indicates the proposed method collects more reward than the corresponding baseline algorithm. Note that against Optimal is always lower than 100%.
Note that we cannot provide other reinforcement since, to the best of our knowledge (for the class NP-hard molti-rrobo/mmaciine scheduling problems with decaying rewards), this paper is the first to propose a reinforcement learning-basee heuristic.
-aaning-based heuristics as additional baselines
6.4 Performance test.
Performance tested under four environments: deterministic/linear rewards, determinis- tic/nonlinear rewards, stochastic/linear rewards, stochastic/nonlinear rewards. See Table I Our method achieves near-optimality for linear/deterministicc rewards with 3% fewer rewards than optimal on average. The standard deviation for is provided in parentheses. For other environments, we see that the %SGA ratio for linear/deterministic is well maintained. Due to dataset generation's dynamic programming computation complexity, we only consider 8 robots/50 tasks at maximum. We considered larger size problems in IPMS experiments discussed in Appendix A.
6.5 Transferability test.
Table 2 provides comprehensive transfcrability test results. The rows indicate training conditions, while the columns indicate testing conditions. The results in the diagonal cells in red (cells with the same training size and testing size) serve as baselines (direct testing). The results in the off- diagonal show the results for the transferability testing and demonstrate how the algorithms trained with different problem sizes perform well on test problems (zero-shot transfer). We can see that lower-direction transfer tests (trained with larger size problems and tested with smaller size problems) show only a small loss in performance. For upper-direction transfer tests (trained with smaller size problems and tested with larger size problems), the loss was up to 4 percent.
6.6 Scalability analysis.
For training complexity, we measured the training time required to achieve 93% optimality considering a deterministic environment with linear rewards. Table 4 shows that training time may not necessarily increase as problem size gets larger, while the performance fairly maintained.
MRRC can be formulated as semi-MDP (SMDP) based multi-robot planning problem (e.g., Omid shafiei et al. 2017)). This problem's complexity with R robots and T' tasks and maximum time horizon is O (RR/T!(R- "). In our proposed method, this complexity is addressed by combi- nation of two complexities: computational complexity and training complexity. For computational
complexity of joint assignment decision at each timestep is (( See Appendix L for details.
7 Concluding Remarks
In this paper, addressed the challenge of developing near-optimal learning- based method for solving NP-hard multi-roboo/mmachine scheduling problems. We developed a theory of mean- field inference for scheduling problems and corresponding theoretically justified GNN method to precisely infer the Q-function. We addressed the scalability issue of Fitted Q- Q-Iteration methods for multi-roboo/machine scheduling problems by providing a polynomial- algorithm with a provable performance guarantee. Simulation results demonstrate the effectiveness of the our methods.
Acknowledgement
Jinkyoo Park was supported by Institute of Information & communications Technology Planning Evaluation (ITPP) grant funded by the Korea governnentMSSTTTy222-00000 Development of Collective Collaboration Intelligence Framework for Internet of Autonomous Things).
10

---

References
Agarwal, A., Jiang, N., and Kakade, M. Reinforcement learning: Theory and algorithms. Technical report, 2019.
Ahn, S., Seo, Y., and Shin, J. Learning what to defer for maximum independent sets. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 134-144. PMIR, 13- 18 Jul 2020.
Bello, I., Pham, H., Le, Q- V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv preprint Xiv: 161 .09940, 2016.
Chen, X. and Tian, Y. Learning to perform local rewriting for combinatorial optimization. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F,, Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
da Costa, P. R. d. O., Rhuggenaath, J., Zhang. Y., and Akcay, A. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. Pan, S. J. and Sugiyama, M. (eds.), Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, pp. 465-480, Bangkok, Thailand, 18-20 Nov 2020. PMLR.
Dai, H., Dai, B., and Song. L. Discriminative Embeddings Latent Variable Models for Structured Data. 48:1-23, 2016. doi: 1603.05629.
Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., and Song, L. Learning Combinatorial Optimization Algorithms over Graphs. (Nips), 2017.
Ekici, A. and Retharekar, A. Multiple agents maximum collection problem with time dependent rewards. Computers and Industrial Engineering, 64(4):1009- 1018, 2013. ISSN 03608352. doi: 10. 2013.01.01 URL http://dd doi
Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model arbitrarily large tsp instances, 2021.
Google. Google Roolo,,, 2012. httppppp///veellpprrroooooo//o//
Gurobi Optimization, L. Gurobi optimizer reference manual, 2019. URL http::/www: www.wg.r.b..... com
Han-Lim Choi, Brunet, L.,, and How, J. Consensus- -aased Decentralized Auctions for Robust Task
Allocation. IEEE Transactions on Robotics, 25 aug 2009. ISSN 1552-3098. doi: 10.1 10.1109/TR02200.222220
Joshi, C. K., Cappart. Q., Rousseau, L.-M., Laurent, T., and Bresson, X. Learning tsp requires rethinking generalization, 2020.
Kang, H. and Kumar, P. R. ++r apprrxiiie policy and fitted q-iteration Unpublished working pdf 2021.
for problems with large action space.
paper
(" pettp://people... tamu. tamu.edu/ BaakkangKKngkumar///
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348-6358, 2017.
Kim, M., Park, J., et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
Koenig, S., Tovey, C., Lagoudakis, M., Markakis, V., Kempe, D., Keskinocak, P., Kleywegt, A., Meyerson, A., and Jain, S. The power of sequential single-item auctions for agent coordination. In AAAI, volume 2006, pp. 1625-1629, 2006.
Koller, D. and Friedman, Probabilistic graphical models principles and techniques, page 449-453.
The MIT Press, 1st edition, 2009. ISBN 9780262013192.

---

Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018.
Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems, 2021.
Kurz, M. E., Askin, R. G., Kurzy, M. E., and Askiny, R. G. Heuristic scheduling of parallel machines with seguuence-dependen set-up times. International Journal Production Research, 39(16): 3747-3769, 2001. ISSN 0020-7543. doi: 10. N..10000002055541100000
Long, Q.. Zhou, Z., Gupta, A., Fang, F., Wu, Y., and Wang, X. Evolutionary population curriculum for scaling multi-agent reinforcement learning, 2020.
Lu, H., Zhang, X., and Yang. S. A learning based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E. Reinforcement learning for combinatorial optimization: A survey. arXiv preprint 2rXiv:2003.03600, 2020.
minmaxTSPlib. minmax multiple-tsp library. http://pow...uuuuucucocoom////in 2021.
Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M. Reinforcement learning for solving the vehicle routing problem. In Advances Neural Information Processing Systems, pp. 9839-9849, 2018.
Neller, T., DeNero, J., Klein, D., Koenig, S., Yeoh, W., Zheng, X., Daniel, K., Nash, A., Dodds, Z., Carenini, G., Poole, D., and Brooks, C. Model AI Assignments. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 1919-1921, 2010.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14(1):265-2944 1978.
Omidshafiei, S., Moohhmmdh,mmaiii, A., Amato, C., Liu, S., How, J. P., and Vian, J. Decentralized control of multi-robot partially observable Markov decision processes using belief space macro- actions. The International Journal of Robotics Research, 36(2):231-255 2017. doi: 10.1177/
0278364917692864.
Parisotto, E., Song, F., Rae, J., Pascanu, R., Gulcehre, C., Jayakumar, S., Jaderberg. M., Kauf- man, L., Clark, A., Noury, S., et al. Stabilizing transformers for reinforcement learning. In International conference on machine learning, pp. 7487-7498. PMLR, 2020.
Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R. Y., Chen, X., Asfour, T. Abbeel, P., and Andrychowicz, M. Parameter Space Noise for Exploration. pp. 1-18, 2017.
Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning, 2018.
Smola, A., Gretton, A., Song, L., and Schölkopf, B. A hilbert space embedding for distributions, In International Conference on Algorithmic Learning Theory, pp. 13-31. Springer, 2007.
Sriperumbudur, B. K., Gretton, A., Fukumizu, K., Lanckriet, G., and Schölkopf, B. Injective hilbert space embeddings of probability measures. 21st Annual Conference on Learning Theory (COLT 2008), pp. 111-122. Omnipress, 2008
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, Z., Tuyls, K., and Graepel, T. Value-decomposition networks for cooperative multi-agent learning, 2017.
van Hasselt, H., Guez, A., and Silver, D. Deep Reinforcement Learning with Double Q-learning 2015.
Wu, Y., Song, W., Cao. Z., Zhang, J., and Lim, A. Learning improvement heuristics for solving routing problems, 2020.
12


Reviews:
[{"review_id": "Pvq_fyKH2a", "reviewer": "Reviewer_JnjH", "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.", "questions": "Why the MRRC problem was chosen? Is it a popular studying topic?\n\nIn line 88 the set $\\{1,\\ldots,N\\}$ is not indexed. $N$ must depend on $k$, doesn’t it?\n\nIn 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.\n\nIn line 126 there’s a typo. Probably not “task locations”, but “robot locations”.\n\nIn line 339 double “the”.\n\nThe 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.\n", "limitations": "The article does not have potentially negative societal impact.", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nThere are many typos in the work: missing parentheses, extra whitespaces in the center of words, incorrect use of plural form of words.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KFl98TeSTVx", "reviewer": "Reviewer_99dG", "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.  \n", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis 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. \n\nWeaknesses: \n\nThe 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. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DTkklHRWc13", "reviewer": "Reviewer_VzR4", "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.", "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.\n2. Can you give a formal statement of the (optimisation/assignment) problem you're trying to solve?\n3. Is the mechanism described in 4.5 used at train or inference time?\n4. What is the difference between the mechanism in 4.5 a Single Sequential Item auctioning?\n5. What's the baseline for the transferability results?\n6. Why 93% optimality? How is this determined?\n", "limitations": "Limitations are not obviously discussed. ", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nI 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.\n\nIn 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). \n\nThe 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?\n\nDespite the level of formality introduced, there isn't really a formal statement of the problem being solved. \n\nIt's hard to grasp the experimental domain without an image in the main paper.\n\nWhat\\s the base;om\n\nThe 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.\n\nThe 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. \n\nFollowing 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).\n\nSection 4.5 seems to be describing a Single Sequential Item auction. Is that correct?\n\nThe 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\"?\n\nI'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. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept