{"id":"a8ce5c8b-407b-46d1-a627-df5dfed00cdc","arxiv_id":"2501.19063","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A DQN plus GNN policy matches or slightly beats simple greedy heuristics on a newly formalized job allocation problem, with limited statistical support and no released artifacts.","lead":"This report applies deep reinforcement learning with graph neural networks to a job allocation problem, where each person can take any non-conflicting set of jobs. It reports near-optimal approximation ratios on synthetic and hospital data, but the claimed advantage over greedy baselines is small, one dataset favors the baseline, and no code or data are provided.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Sec. 4 transition does not enforce Definition 2 on directed conflicts, so a policy can produce allocations that violate the stated JAP; reported approximation ratios therefore do not evaluate the claimed problem.","rationale":"The central empirical claim is that the GNN 'demonstrates superior performance across each dataset' and 'outperforming baseline algorithms' on the JAP. For that to be true, the training and evaluation loops must solve the constrained problem in Definition 2. I find a load-bearing defect there: the transition function only removes outgoing conflicts, while the feasibility condition forbids conflicts regardless of orientation. The 1-person/2-job rollout above yields an infeasible final allocation, so the MDP's feasible-solution guarantee is false. This is not an artifact of the appendix or a disagreement with external consensus; it is an internal inconsistency. If C is guaranteed symmetric, the paper should state it and verify the datasets; if not, the transition (and Algorithm 1) must remove incoming arcs too. Because every experiment in Tables 1-2 and Fig. 5 uses this transition, the reported ratios cannot be interpreted as approximation ratios for the stated JAP. The reader's weakest assumption (no per-job capacity) is also real and important: with job uniqueness, the problem changes and the MDP no longer applies. However, the transition/definition mismatch is more fundamental and requires no new assumptions. I note the paper does disclose the exploding loss in Appendix B and uses a plausible GNN/RL pipeline, but disclosure of a symptom does not repair the formal gap. No code, data, or seeds are provided, so an empirical recheck cannot substitute for the formal fix. Since this concern invalidates the evaluation target as written, I maintain the REJECT verdict; no adjustment is needed relative to the reader's verdict.","tokens_in":9753,"tokens_out":11581,"duration_ms":111317,"concrete_test":"Run a single environment rollout on the 1-person, 2-job instance P={p0}, J={ja,jb}, S={{p0,ja},{p0,jb}}, C={(ja,jb)} with Algorithm 1's transition: first take action {p0,jb}, then {p0,ja}. If the final allocation contains both edges, the transition does not enforce Definition 2. To settle the intended semantics, inspect the adjacency construction for Planny and synthetic data: if any conflict is stored as only one directed arc while Definition 2 treats conflicts as symmetric, the evaluation target is inconsistent; if C is always symmetric, rerun the same rollout with C={(ja,jb),(jb,ja)} and verify the second action is eliminated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is an inconsistency between the feasibility constraint in Definition 2 and the MDP transition in Sec. 4. Definition 2 forbids assigning to the same person two jobs j_i and j_k whenever (j_i,j_k)∈C or (j_k,j_i)∈C. The transition, however, after choosing {p,j} removes only the outgoing conflict edges {p,j_i} with (j,j_i)∈C; it never removes incoming edges {p,j_i} with (j_i,j)∈C. If a conflict is represented by a single directed arc, a policy can create a violation: take P={p0}, J={ja,jb}, S={{p0,ja},{p0,jb}}, C={(ja,jb)}. If the agent first selects {p0,jb}, the transition removes {p0,jb} but leaves {p0,ja}; the agent can then select {p0,ja}. The final allocation {{p0,jb},{p0,ja}} satisfies the transition rule yet violates Definition 2, because (ja,jb)∈C. Since every training episode and every reported approximation ratio is generated through this transition, the learned policy and its evaluation are not solving the problem stated in Definition 2. This is an internal correctness issue: either C must be closed under reversal, or the transition must also delete incoming conflicts, or Definition 2 must be weakened; the paper does none of these. The Appendix's exploding loss is consistent with this defect, but the formal argument stands independently of the experiments.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a Job Allocation Problem (JAP) in which a maximum-cardinality set of person-job assignments is sought under per-person conflict constraints. It formulates the JAP as a Markov Decision Process and proposes a Double DQN agent whose Q-function is a Graph Attention Network with Context-Aware Embedding (CAE) modules. Experiments compare the GNN against greedy, random, and untrained baselines on synthetic Erdős–Rényi and Barabási–Albert graphs and on a real-world hospital dataset (Planny), including out-of-distribution tests. The abstract and conclusion claim that the GNN consistently outperforms baselines and generalizes well.","tokens_in":9949,"tokens_out":6060,"duration_ms":49989,"significance":"If the claims were rigorously established, the paper would provide a useful empirical demonstration of RL+GNN for graph-constrained allocation problems. The architecture design—splitting the graph into selection and conflict subgraphs and combining embeddings symmetrically—is clearly described, and the paper provides hyperparameters, dataset statistics, and out-of-distribution experiments, which are positive elements. However, the central formalization is internally inconsistent: the MDP transition does not enforce the feasibility constraint of the stated optimization problem. In addition, the problem as defined lacks any job-capacity constraint, so it does not match the motivating hospital scenario and decomposes into trivial per-person independent-set problems. Finally, the experimental evidence does not support the claim of consistent outperformance, and the paper itself reports unstable training. These are load-bearing issues, so the manuscript cannot be accepted in its current form.","major_comments":[{"comment":"The MDP transition defined in §4 and Algorithm 1 removes only outgoing conflict edges, so it does not enforce the feasibility constraint of Definition 2. With P={p0}, J={ja,jb}, S={{p0,ja},{p0,jb}}, and C={(ja,jb)}, selecting {p0,jb} first removes {p0,jb} and leaves {p0,ja}; the agent may then select {p0,ja}, yielding a final allocation containing both conflicting assignments for p0. This violates Definition 2 even though every step is allowed by the transition. Consequently, the policy learned and the approximation ratios reported in §6 evaluate a different problem from the one stated in Definition 2. Either C must be treated as symmetric (or closed under reversal) or the transition must also delete incoming conflict edges; the manuscript does neither.","section":"§4, transition function (Definition 3 and Algorithm 1)"},{"comment":"The formal problem places no constraint on how many people can be assigned the same job: a job j may appear in any number of selected edges {p,j}. For the motivating hospital (Planny) scenario, and for job allocation more generally, each job is a task that must be executed once by a single person. As stated, the JAP decomposes into independent maximum-independent-set problems on the conflict graph induced by each person's eligible jobs, so the objective is a sum of per-person optima. This is a substantially weaker problem than the intended allocation problem, and the paper neither states nor justifies the absence of a job-capacity constraint. The MDP, experiments, and conclusions all inherit this modeling choice.","section":"Definitions 1 and 2"},{"comment":"The statement in §6.2 that the GNN 'demonstrates superior performance across each dataset' is not supported by the reported numbers. On Barabási–Albert, Greedy achieves 1.000 while the GNN reaches 0.999 ± 0.002; on Planny, the GNN's 0.989 ± 0.013 and Greedy's 0.987 ± 0.026 overlap well within one standard deviation. Only on Erdős–Rényi is the gap (0.981 vs 0.962) larger than the standard deviations. The abstract and conclusion overstate the evidence for consistent outperformance.","section":"§6.2, Table 1"},{"comment":"Appendix B reports that the training loss explodes (Fig. 6) and that the normalized Q-values are not monotonically decreasing (Fig. 7), then asserts without further evidence that the model 'was still able to learn a good order of states'. Since Double DQN and PER were introduced precisely to stabilize training, this admitted instability is a serious concern for the validity of the learned Q-function. Moreover, the high approximation ratios of the Random baseline (0.969 on Planny, 0.996 on Barabási–Albert) and of the Untrained GNN (0.999 on Barabási–Albert) suggest that the problem instances are not particularly challenging and that the reported GNN performance may not reflect a genuinely learned policy. The paper should provide convergence or validation evidence before attributing the results to learning.","section":"Appendix B"}],"minor_comments":[{"comment":"The reward function is written as R: S × A → S; it should map to a real number, e.g., R: S × A × S → R or R: S × A → R.","section":"Definition 3"},{"comment":"The priority update uses |δi|, but δi is not defined in that loop; it should be |δk| from line 17.","section":"Algorithm 1, line 18"},{"comment":"The sentence 'In this work, we utilize graph attention networks in this work since we are learning representations of edges' contains a redundant 'in this work'.","section":"§5.1"},{"comment":"The reference to Bachlechner et al. (2020) has a garbled author list ('Huanru Henry Majumder, Bodhisattwa Prasad Mao' should be 'Bodhisattwa Prasad Majumder, Henry Mao'); please correct it.","section":"References"},{"comment":"The plots in Figures 6 and 7 are described only in the text; please add axis labels and clarify what is plotted (e.g., training step vs loss, timestep vs normalized Q-value) to make them self-contained.","section":"Figures 6 and 7"}],"recommendation":"reject","confidential_remarks":"For the editor: this manuscript reads as a single-author project report rather than a fully developed research paper. The formal inconsistency between the problem definition and the MDP transition is fundamental, and the empirical evidence does not support the stated conclusions. The paper would need a re-formulation of the problem, a corrected MDP, and new experiments before it could be considered for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You asked about Quaedvlieg's arXiv:2501.19063. Bottom line: it's a decent application of standard DQN+GAT to a scheduling problem, but the core MDP has a feasibility bug that invalidates the reported results, and the headline claims don't survive their own Table 1.\n\nWhat's actually new: the problem is formalized as a graph with selection and conflict edges, and the CAE module that splits the graph into two subgraphs before attention is a sensible design. The out-of-distribution experiments, while small, are a reasonable attempt to probe generalization. The writing is clear and the related work is fine.\n\nThe soft spots are substantial. First, the transition in Sec. 4 removes only outgoing conflict edges: after selecting {p,j}, it deletes {p,ji} when (j,ji) is in C, but not when (ji,j) is in C. If C contains only (ja,jb), selecting {p,jb} leaves {p,ja} available, and the agent can then select it, producing a final allocation that violates the intended conflict constraint. The paper says the transition 'maintains feasibility,' but it doesn't. Since every episode and every reported approximation ratio goes through this transition, the experimental evaluation is not solving the problem as described. This is the paper's biggest problem, and it's internal. Second, the formal Definition 2 appears to have a typo—the implication should require i ≠ k for conflicting jobs, not i = k—and even a corrected reading doesn't rescue the transition. Third, the performance claims are weaker than the abstract suggests: on Barabási–Albert, Greedy achieves 1.000 and the GNN 0.999; on Planny the gap is 0.989 vs 0.987 with overlapping standard deviations. There are no significance tests, no code, no seeds, and the exact method used to compute the 'optimal' solutions for the approximation ratios is never described. The appendix's exploding loss is consistent with the transition defect.\n\nOne more note: because the formulation has no job-capacity constraint, the problem reduces to independent per-person maximum independent set problems; calling it a novel problem overstates the contribution.\n\nWho is this for? A reader curious about RL+GNN for scheduling might skim it, but it's not a reliable source in its current form. I would not send it to a serious referee. If the transition is fixed, the experiments are redone, and the code and seeds are released, it could become a modest application paper.","headline":"Sensible RL+GNN application undermined by a feasibility bug in the MDP transition and unsupported performance claims.","tokens_in":10594,"tokens_out":5811,"would_cite":false,"duration_ms":49965,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper argues that a reinforcement learning agent with a graph attention network learns near-maximal conflict-free job allocations, outperforming greedy and random baselines on hospital and synthetic data and generalizing to…","keywords":["job allocation problem","reinforcement learning","graph neural networks","graph attention networks","deep Q-learning","combinatorial optimization","scheduling","out-of-distribution generalization"],"falsifier":"Evaluate the trained GNN on instances in which each job has capacity one (each job executed at most once), computing exact optima by enumeration for small graphs; under the paper's transition rule the same job can be selected by many people, so feasible allocation sizes would diverge from the reported near-optimal ratios. A second, immediate check is the paper's own Table 1: on the Barabási–Albert dataset the GNN's mean approximation ratio is 0.999 ± 0.002 while Greedy attains 1.000, so the assertion of superiority across each dataset is falsified on the reported numbers.","tokens_in":9431,"feed_emoji":"🤖","tokens_out":11241,"duration_ms":99423,"temperature":0.7,"pith_summary":"The paper introduces the Job Allocation Problem (JAP), in which a set of people must be assigned to as many jobs as possible while respecting per-person conflict constraints between jobs, and proposes to solve it with reinforcement learning instead of labeled data. The agent observes the allocation problem as a graph with selection edges (who can do which job) and conflict edges (which jobs clash for the same person), takes one assignment per step, and receives a reward of 1 for each valid assignment, making the episode return equal to the allocation size. The paper claims the resulting graph-attention Q-network outperforms greedy, random, and untrained baselines on a hospital dataset and two synthetic graph families, and that it generalizes to out-of-distribution instances of different size and density. The payoff, if true, is a scheduling method that needs no manual annotation, avoiding a key bottleneck for supervised learning on NP-hard combinatorial problems.","feed_headline":"RL agent learns near-optimal job allocation without labels","feed_subtitle":"Graph-attention Q-network scores 98–99 percent of optimal and transfers to new hospital and synthetic graphs.","key_machinery":"The central machinery is the MDP transition function together with a Context-Aware Embedding (CAE) module. The CAE module splits a job-allocation graph into a selection subgraph (people–jobs edges) and a conflict subgraph (job–job edges), passes each through its own graph attention layer (a message-passing layer that weights neighbor updates by learned attention), and merges the job representations symmetrically via $f_{\\theta_2}(x,y)=1+\\lambda\\,\\mathrm{FC}_{\\theta_2}([x\\Vert y])$ averaged over both argument orders; the Q-value for assigning person $p$ to job $j$ is the dot product of their final embeddings. The transition function removes the chosen selection edge along with every conflicting edge for that person, so every episode yields a feasible allocation and the undiscounted cumulative reward equals the size of the allocation.","core_discovery":"The paper's central discovery, stated on its own terms, is that a Double DQN agent with a graph attention network can learn near-maximal conflict-free job allocations without any supervision. On the three test collections the trained GNN attains mean approximation ratios of 0.989 on the Planny hospital data, 0.981 on Erdős–Rényi graphs, and 0.999 on Barabási–Albert graphs, while the greedy baseline attains 0.987, 0.962, and 1.000 respectively; out-of-distribution models also reach or exceed the greedy baseline on unseen datasets and scale to larger Erdős–Rényi instances. The paper interprets these results as evidence that reward-driven trial and error, combined with graph-structured representation learning, is a viable route to optimizing job allocation and related combinatorial scheduling problems.","pith_inferences":["The formalization as written imposes no capacity constraint on jobs, so each job can be assigned to every connected person; enforcing 'each job is done once' would require a different transition function and new experiments, and the reported ratios should not be read as evidence for that realistic variant.","On the Barabási–Albert data all methods are near-perfect (0.996–1.000), which suggests those instances are easy for the greedy heuristic; a harder, conflict-dense test would better reveal what the learned policy adds beyond greedy behavior.","The exploding Q-values reported in Appendix B indicate the network's absolute predictions are not calibrated even though the induced action ordering may be useful; a terminal-state bonus or shaped reward could stabilize training and improve transfer.","A baseline that runs a standard maximum-independent-set heuristic on each person's conflict neighborhood would quantify the contribution of the learned GNN representation; the paper does not include such a comparison."],"forward_implications":["If the reported ratios hold, a single trained graph network could assign jobs in real time on a hospital ward without re-solving an optimization problem for each new request set.","The reward-only recipe (no labels, a reward of 1 per valid assignment) can be applied to other constraint problems expressible as bipartite-plus-conflict graphs, such as nurse rostering or room allocation.","The out-of-distribution results imply a model trained on one set of hospitals or jobs could be transferred to another site with different numbers of people, jobs, and conflict densities.","Because the formulation decomposes into per-person maximum independent set problems, the learned Q-values effectively solve a family of maximum independent set instances, so the architecture is a candidate for structured MIS learning."],"supporting_citations":[{"why":"provides the graph attention layer used in both subgraphs of the CAE module.","marker":"Veličković et al., 2018"},{"why":"supplies the idea of splitting the graph into separate subgraphs for semantically different edge types.","marker":"Zhang et al., 2022"},{"why":"provides the residual fusion form $1+\\lambda\\,\\mathrm{FC}$ used to combine job embeddings.","marker":"Bachlechner et al., 2020"},{"why":"provides the Deep Q-Learning algorithm that the training pipeline is built on.","marker":"Mnih et al., 2015"},{"why":"supplies Double DQN, used to stabilize learning and reduce overestimation.","marker":"Van Hasselt et al., 2016"},{"why":"supplies prioritized experience replay, used to sample transitions by Q-learning error.","marker":"Schaul et al., 2015"}],"fun_headline_variants":["Graph RL allocates jobs near-optimally without labels","RL+GNN hits 99% optimal job allocation","Unsupervised graph RL attains near-optimal job allocation","GNN-guided RL finds near-optimal job sets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a job can be assigned to every qualified person at once, with no constraint that each job is performed only once; without that premise the problem no longer separates into per-person maximum-independent-set subproblems, and the MDP transition and the reported approximation ratios no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Graph RL allocates jobs near-optimally without labels","RL+GNN hits 99% optimal job allocation","Unsupervised graph RL attains near-optimal job allocation","GNN-guided RL finds near-optimal job sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001464,"raw_usage":{"total_tokens":5833,"prompt_tokens":835,"completion_tokens":4998,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":451,"completion_tokens_details":{"reasoning_tokens":4932}},"tokens_in":451,"tokens_out":4998,"duration_ms":34455,"temperature":1.0,"reasoning_tokens":4932,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T21:27:03.448236+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the trained GNN on instances in which each job has capacity one (each job executed at most once), computing exact optima by enumeration for small graphs; under the paper's transition rule the same job can be selected by many people, so feasible allocation sizes would diverge from the reported near-optimal ratios. A second, immediate check is the paper's own Table 1: on the Barabási–Albert dataset the GNN's mean approximation ratio is 0.999 ± 0.002 while Greedy attains 1.000, so the assertion of superiority across each dataset is falsified on the reported numbers.","supporting_citations":[{"cited_title":"Learning to search for job shop scheduling via deep reinforcement learning, 2022","cited_arxiv_id":null,"evidence_quote":"supplies the idea of splitting the graph into separate subgraphs for semantically different edge types."}],"review_version":1}