{"id":"b4ff2743-4e3a-4bc8-95ee-c07327a22444","arxiv_id":"2411.10558","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"MAPF-EGT, an evolutionary game theory policy learner with weighted automaton rewards, is reported to beat deep RL baselines on large-grid multi-agent pathfinding.","lead":"This paper trains homogeneous robot teams using evolutionary game theory, with weighted automata encoding goals like reaching targets quickly while avoiding obstacles. The authors report up to 30% shorter paths and much faster training than reinforcement learning baselines on large grids.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's update rule (line 13) injects an extra π_k factor and a hyperparameter α into the replicator update, so the resulting action probabilities do not sum to 1; the described training procedure is mathematically invalid, undermining the reported empirical claims.","rationale":"The paper's headline contributions are empirical: MAPF-EGT is said to cut path length by roughly 30% and to run an order of magnitude faster than deep RL. Those numbers can only be meaningful if the training loop is specified precisely enough to reproduce. I reviewed Algorithm 1 against the replicator equation in Section 4.1. Equation (4) is the standard frequency-dependent update that preserves probability normalization. Line 13 of the algorithm, however, contains an extra π_k(s,a) multiplier and an α scaling factor inside the update. Summing the written right-hand side over actions does not yield 1 unless f is constant and α=1; line 14's mixture with the uniform policy does not restore normalization because it is a convex combination of a sub-distribution and a distribution, which yields a sub-distribution. Hence the pseudocode cannot define a policy. This is not merely a missing proof: it is an algorithmic inconsistency that would prevent the method from running as described. The reader's verdict was CONDITIONAL, citing convergence concerns; the normalization defect is more elementary and directly attacks reproducibility. It may be a typo, in which case correction and code release would resolve it, but until then the empirical claims are unverifiable. I therefore keep the verdict CONDITIONAL, with the condition being correction of the update rule and verification that the reported results are produced by the corrected algorithm.","tokens_in":14747,"tokens_out":12120,"duration_ms":114963,"concrete_test":"Set up a one-state MDP with two actions, initial policy π(a1)=π(a2)=0.5, fitness values f(a1)=2, f(a2)=1, and hyperparameters α=0.5 and w=0. Apply Algorithm 1 line 13 followed by line 14, then compute the sum of the two updated action probabilities. If the sum is not 1, the update does not define a probability distribution, confirming that the published training procedure is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that MAPF-EGT outperforms RL baselines rests on the policy update in Algorithm 1. Section 4.1, Equation (4), defines the replicator update as π_{i+1}(s,a) = π_i(s,a) f(s,a) / Σ_{a'} π_i(s,a') f(s,a'), which preserves normalization. However, Algorithm 1 line 13 writes πnew_{k+1}(s,a) ← πnew_k(s,a) · α · (πnew_k(s,a) f(s,a) / Σ_{a'} πnew_k(s,a') f(s,a′)), introducing an extra πnew_k(s,a) factor and a scaling α. Summing this right-hand side over actions gives α · Σ_a [π_k(a)^2 f(a)] / [Σ_b π_k(b) f(b)], which is not 1 for α≠1, and in general is below 1 even for α=1 unless f is constant. Line 14 mixes this sub-distribution with a uniform policy, but a convex combination of a distribution and a sub-distribution is still a sub-distribution, so the output is not a valid stochastic policy. The paper lists α as a tunable hyperparameter and does not state α=1; if α=1 is silently used, the 'learning rate' is vacuous and the extra π_k factor remains inconsistent with Equation (4). Either way, the algorithm as written cannot be executed, and the reported 'nearly 30% path-length reduction' and 'order-of-magnitude speedup' are not reproducible from the published pseudocode.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MAPF-EGT, a training method for homogeneous multi-agent path finding where goal locations are unknown a priori. The method uses weighted automata to define trajectory-level rewards that reward expeditious, collision-free goal reaching, and updates a shared stochastic policy using an evolutionary game theory replicator-style rule (Section 4.1, Eq. (4)). The authors claim that, compared with deep RL baselines (PPO), tabular Q-learning, Monte Carlo, and A*, their algorithm reduces path length by nearly 30% in large grids, is at least an order of magnitude faster, and scales better with the number of agents (Abstract, Section 5).","tokens_in":15094,"tokens_out":3325,"duration_ms":32737,"significance":"If the algorithm and experiments are correct, the paper makes two useful contributions: weighted automata rewards that go beyond deadline satisfaction to expeditiousness, and an evolutionary, tabular, shared-policy training method that avoids neural networks and large sample counts. The paper explicitly ships heuristic convergence reasoning and acknowledges sub-optimality, which is honest. However, the central algorithmic description in Algorithm 1 is mathematically inconsistent with the stated replicator update, and the empirical section does not provide enough numerical detail to verify the headline claims; the significance is therefore conditional on correcting these issues.","major_comments":[{"comment":"The update rule as written is not a valid stochastic policy update. It computes πnew_{k+1}(s,a) ← πnew_k(s,a) · α · (πnew_k(s,a) f(s,a) / Σ_{a′} πnew_k(s,a′) f(s,a′)). Summing this expression over a gives α · Σ_a π_k(a)^2 f(a) / Σ_b π_k(b) f(b), which is not 1 in general, even for α = 1. The subsequent mixing with the uniform distribution in line 14 cannot restore normalization, because a convex combination of a distribution and a sub-distribution is still a sub-distribution. Thus the output of Algorithm 1 is not a probability distribution over actions, and the described training procedure cannot be executed as published. The authors must correct line 13 to match Eq. (4)—that is, remove the extra π_k(s,a) factor and either set α = 1 or provide a normalization step that makes the update a valid distribution.","section":"Section 4.1, Algorithm 1, line 13"},{"comment":"The key convergence argument is asserted, not proved. The text claims 'The evolutionary update guarantees that ... the value of the state s increases,' but provides no proof that the batch-sampled fitness estimates f(s,a) and f(s) satisfy the conditions needed for replicator-style monotonicity. Since these fitnesses are empirical batch returns, sampling noise or estimation bias can easily break the monotonicity property. The manuscript itself concedes that optimality would require a contraction mapping and defers that proof. Given that the termination condition (η_k − η_{k−1} < δ) and the complexity bound O((η*−η0)/δ · T · B) both depend on this asserted monotone improvement, the authors should either supply a rigorous proof under explicit assumptions or clearly state that termination and convergence are heuristic.","section":"Section 4.1, 'Termination and convergence'"},{"comment":"The central empirical claims—'nearly 30%' path-length reduction, 'order-of-magnitude' speedup, and better scaling with agent count—are not supported by reproducible numerical evidence. The paper reports only qualitative plots and does not provide means, standard deviations, number of seeds, or a table of the exact values behind Figure 5. It also does not report the hyperparameters used for MAPF-EGT (α, ν, ε, δ, batch size B, horizon T, discount γ) or the reward weights a, b, c. Without these details, the reader cannot verify the headline numbers or reproduce the experiments. Please include full experimental settings and quantitative results, preferably with error bars.","section":"Section 5 and Figure 5"}],"minor_comments":[{"comment":"There is a typo in the caption: 'Time steps to reach the goaal' should read 'goal'; also, 'Fig. d' should be 'Fig. (d)' for consistency with the other subfigures.","section":"Figure 5 caption"},{"comment":"The transition sampling notation contains a typo: 'si t ∼ ∆(s′|s, a)' should read 'si_{t+1} ∼ ∆(s′|s, a)', since the next state is sampled, not the current one.","section":"Section 2, Definition 1"},{"comment":"The constraint 'b ≥ c > a·T' appears, but the paper does not explicitly state that these weights must also ensure that a successful, collision-free trajectory has a positive total reward and that any trajectory with a collision or a missed deadline has non-positive reward; making this explicit would sharpen Proposition 1.","section":"Section 3, Eq. (2)"},{"comment":"The text cites reference [2] as 'AvSTL', but the bibliography entry is about 'Time Robustness in MTL and Expressivity in Hybrid System Falsification'; please clarify the connection or correct the citation.","section":"Section 1, related work on AvSTL"}],"recommendation":"major_revision","confidential_remarks":"The extra π_k factor in Algorithm 1 is likely a typographical error that is fixable, but as printed it invalidates the described training procedure. More concerning is the lack of numerical experimental detail, which prevents any independent verification of the central claims. I would require a corrected algorithm, a proof or clearly stated heuristic status of the convergence argument, and full experimental reproducibility data before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's core idea is worth a look: it combines weighted automata (specifically a deterministic WA encoding reach-avoid with expeditiousness penalties) with a tabular evolutionary policy update for homogeneous multi-agent teams. That combination appears to be original. The motivation for weighted automata over boolean temporal logic—distinguishing faster from slower successful trajectories—is sound and clearly explained. The paper also honestly concedes that convergence to an optimal policy would require the update operator to be a contraction, which it does not attempt to prove.\n\nThe soft spots are significant, though. First and most importantly, Algorithm 1 line 13 is inconsistent with Equation (4). Equation (4) is the standard replicator update and preserves normalization. Line 13 introduces an extra \\pi_k(s,a) factor and a scaling \\alpha, so summing the right-hand side over actions gives \\alpha \\cdot \\Sigma_a \\pi_k(a)^2 f(a) / \\Sigma_b \\pi_k(b) f(b), which is not 1 in general. Line 14's convex combination with a uniform policy keeps it a sub-distribution. Thus the described training procedure cannot be executed as written. This is not cosmetic: the experiments in Section 5 must have used a working variant, but the published pseudocode does not reproduce it.\n\nSecond, the empirical section lacks error bars, seeds, exact hyperparameter values, and code. The 'nearly 30%' and 'order of magnitude' claims are unverifiable from the text. Third, the problem statement says agents must avoid collisions with one another, but the reward function f_O only penalizes obstacle states; I see no mechanism for penalizing agent-agent collision. If agents share the grid, this needs to be addressed. Fourth, A* is given the Manhattan-distance heuristic while the other methods are not, making that comparison somewhat lopsided, though the authors do acknowledge this.\n\nWho is this for: people working on automata-based reward shaping or evolutionary policy updates for homogeneous multi-agent systems. The conceptual contribution may be salvageable, but the paper needs a corrected algorithm, released code and data, and a clearer collision model before the empirical claims should be believed.\n\nRecommendation: send it to peer review anyway—the idea is relevant and the flaws are fixable—but any responsible referee should demand a rewritten Algorithm 1, verification of the normalization property, and full experimental details. If the authors deliver that, the paper could be decent.","headline":"Interesting combination of weighted automata and evolutionary policy updates, but the published Algorithm 1 is internally inconsistent with the paper's own replicator equation, so the headline empirical claims cannot be trusted as written.","tokens_in":15606,"tokens_out":3540,"would_cite":false,"duration_ms":46426,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A22","68T42","68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"A replicator-dynamics policy update, trained on weighted-automaton rewards, outperforms deep RL by nearly 30 percent in path length on large multi-agent grid worlds.","keywords":["multi-agent path finding","weighted automata","evolutionary game theory","replicator dynamics","reinforcement learning","temporal logic","reward shaping","path planning"],"falsifier":"Run MAPF-EGT on a 100x100 grid with 50 agents, record the batch return $\\eta_k$ after each iteration, and check whether consecutive batches ever satisfy $\\eta_{k+1} < \\eta_k$; the paper's termination guarantee rests on monotonic improvement, so a single observed decrease while the algorithm is still running would falsify that premise. Also, re-running the paper's comparison with a well-tuned PPO over the same wall-clock budget would test whether the ~30% path-length advantage is an artifact of PPO's hyperparameter defaults.","tokens_in":14536,"feed_emoji":"🤖","tokens_out":5300,"duration_ms":47916,"temperature":0.7,"pith_summary":"This paper sets out to solve multi-agent path finding when agents do not know their goal locations in advance and must satisfy timed safety and performance objectives. It argues that weighted automata can specify trajectory-level preferences such as expeditiousness that ordinary deadline-based temporal logic cannot capture, and that evolutionary game theory offers a sample-efficient alternative to deep reinforcement learning for training homogeneous teams. The authors claim that their algorithm, MAPF-EGT, reduces path length by nearly 30% versus state-of-the-art RL on large grids, is at least an order of magnitude faster to train, and scales better with agent count. A sympathetic reader would take the central contribution to be the demonstration that a simple tabular replicator-dynamics update, fed with shared batch trajectories and automaton-derived rewards, can outperform deep RL on this class of tasks.","feed_headline":"Evolutionary game theory cuts multi-agent path length by ~30%","feed_subtitle":"A tabular replicator-dynamics policy beats deep RL in large grids while staying an order of magnitude faster.","key_machinery":"The engine of the method is the replicator update $\\pi_{k+1}(s,a) = \\pi_k(s,a) f(s,a) / \\sum_{a'} \\pi_k(s,a') f(s,a')$, where $f(s,a)$ is the batch-estimated expected return for taking action $a$ in state $s$ and $f(s)$ is the state's expected return. Actions whose estimated fitness exceeds the average are amplified, actions below average are suppressed, and the updated distribution is blended with an annealed uniform exploration policy. The reward signal comes from a four-state weighted automaton that gives $+b$ for a first reach of the goal, $-a$ for each step before reaching it, and $-c$ for a collision, with $b \\ge c > aT$, so that expeditious goal-reaching dominates the optimization.","core_discovery":"The paper claims that trajectory-level temporally extended tasks for homogeneous multi-agent teams can be specified by deterministic weighted automata with discounted-sum valuations, and that maximizing the resulting weighted return via a replicator-dynamics policy update yields a shared stochastic policy that is both safer and more expeditious than policies learned by PPO, Q-learning, Monte Carlo search, or A* in large grid worlds. Concretely, the authors report that MAPF-EGT shortens path length by nearly 30% relative to state-of-the-art RL methods on large grids, trains at least an order of magnitude faster, and scales better as the number of agents grows. They prove that any trajectory with positive weighted-automaton reward satisfies the reach-avoid specification, and that among collision-free trajectories, earlier arrival yields higher reward.","pith_inferences":["The replicator update is a form of natural policy gradient where the step size is implicit in the fitness ratio; formalizing this connection could yield convergence-rate bounds and variance-reduction techniques drawn from policy-gradient theory.","The monotonicity assumption could be tested directly: replacing batch returns with bootstrapped or importance-sampled estimates may fix the noisy-fitness failure mode and is a natural empirical next step.","A direct head-to-head on a standard benchmark suite with the same reward and wall-clock budget would tell whether the ~30% path-length advantage persists outside the paper's grid-world configuration.","The framework's restriction to deterministic automata is not essential; resolving nondeterministic runs with a max over valuations, as the paper notes, would let it handle partial observability or multiple accepting behaviors."],"forward_implications":["If the reported gains hold, homogeneous multi-agent teams can be trained on tabular policies without neural networks, dramatically lowering compute and hardware requirements for warehouse and delivery fleets.","Weighted-automaton rewards provide a language for specifying performance objectives such as 'reach fast, then stay safe' that goes beyond hard deadlines, making reward design more expressive for timed tasks.","Because the policy is shared and updated from pooled trajectories, increasing the number of agents enriches the batch data, so larger fleets should train faster relative to RL baselines.","The convergence guarantee is only to a positive-return, specification-satisfying policy, not to optimality; practitioners must monitor the per-iteration return to detect stalls or oscillation."],"supporting_citations":[{"why":"Supplies the formal definition of weighted automata and their weight semantics.","marker":"[18]"},{"why":"Gives the classic replicator equation that the policy update adapts.","marker":"[41]"},{"why":"The A* baseline against which path length and computation time are compared.","marker":"[23]"},{"why":"The PPO baseline, the deep RL method the paper claims to outperform.","marker":"[52]"},{"why":"The Monte Carlo and Q-learning baselines representing tabular RL methods.","marker":"[56]"},{"why":"The Q-learning update formalism that motivates the convergence discussion.","marker":"[58]"},{"why":"The implementation used for the PPO baseline.","marker":"[47]"},{"why":"The foundational book on evolutionary game theory that motivates the approach.","marker":"[53]"}],"fun_headline_variants":["Evolutionary game theory cuts multi-agent path length by 30%","EGT-based policy trims multi-agent paths 30%, trains 10x faster","Weighted automata + game dynamics reduce path length 30%","Multi-agent routing: evolutionary dynamics beat RL by 30%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The training loop assumes that the average return computed from a batch of sampled trajectories is an unbiased and accurate estimate of each state's and action's true expected return, so that promoting above-average actions strictly increases the value of every visited state.","fun_headline_variants_meta":{"raw":{"variants":["Evolutionary game theory cuts multi-agent path length by 30%","EGT-based policy trims multi-agent paths 30%, trains 10x faster","Weighted automata + game dynamics reduce path length 30%","Multi-agent routing: evolutionary dynamics beat RL by 30%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000556,"raw_usage":{"total_tokens":2634,"prompt_tokens":917,"completion_tokens":1717,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":1639}},"tokens_in":533,"tokens_out":1717,"duration_ms":12949,"temperature":1.0,"reasoning_tokens":1639,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:34:24.855933+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MAPF-EGT on a 100x100 grid with 50 agents, record the batch return $\\eta_k$ after each iteration, and check whether consecutive batches ever satisfy $\\eta_{k+1} < \\eta_k$; the paper's termination guarantee rests on monotonic improvement, so a single observed decrease while the algorithm is still running would falsify that premise. Also, re-running the paper's comparison with a well-tuned PPO over the same wall-clock budget would test whether the ~30% path-length advantage is an artifact of PPO's hyperparameter defaults.","supporting_citations":[{"cited_title":"In: Droste, M., Kuich, W., Vogler, H","cited_arxiv_id":null,"evidence_quote":"Supplies the formal definition of weighted automata and their weight semantics."},{"cited_title":"Chaos: An Inter- disciplinary Journal of Nonlinear Science31(2) (Feb 2021).https://doi.org/10","cited_arxiv_id":null,"evidence_quote":"Gives the classic replicator equation that the policy update adapts."},{"cited_title":"Journal of Machine Learning Research (2021)","cited_arxiv_id":null,"evidence_quote":"The implementation used for the PPO baseline."},{"cited_title":"Cambridge University Press (1982)","cited_arxiv_id":null,"evidence_quote":"The foundational book on evolutionary game theory that motivates the approach."}],"review_version":1}