{"id":"5168f110-b5ea-4037-b9b4-1440853867a8","arxiv_id":"2411.11099","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"MMQ mitigates relative over-generalization in decentralized MARL by taking the maximum over sampled next states predicted from quantile bounds.","lead":"MaxMax Q-Learning (MMQ) is a new fully decentralized multi-agent reinforcement learning algorithm that counters relative over-generalization by sampling possible next states from learned quantile bounds and updating Q-values with the maximum over them. The paper shows MMQ frequently beats existing decentralized baselines in cooperative tasks, including predator-prey, navigation, and MuJoCo control.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MMQ's central claim depends on the unverified premise that the quantile-predicted next-state set contains the ideal next state s'*, yet the paper only checks coverage of observed transitions, which is insufficient under relative over-generalization.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the algorithm's optimism and Theorem 4.1 rely on the estimated next-state set covering the ideal next state, yet the paper provides no direct evidence that this ideal transition is included when it is rare. My reading confirms this is the most fragile point in the argument. The paper's own caveat ('we cannot guarantee') and the misdirected Figure 5b strengthen the concern. I do not find a more fundamental flaw that would demand rejection; the theory is conditional on a plausible but unverified premise, and the empirical results are reasonably extensive. One concrete test—logging s'* inclusion and ablating the replay buffer to exclude optimal-joint-action transitions—would settle whether the premise holds in practice. Therefore the verdict should remain CONDITIONAL, with the condition being the explicit demonstration of ideal-state coverage or a revised theoretical justification that does not require it.","tokens_in":21027,"tokens_out":2270,"duration_ms":88937,"concrete_test":"Instrument the released MMQ code in the Differential Game and Cooperative Navigation environments to log, at every update, whether the true ideal next state s'* = f_env(s, a_i, pi*_{-i}(s,a_i)) (computed by enumerating all other-agent actions under the known environment) lies inside the predicted quantile bounds and inside the sampled set ^S. Then run a filtered-buffer variant in which all transitions generated while another agent takes its optimal action are removed from the replay buffer. If the inclusion rate is low and MMQ fails without those transitions, the premise is load-bearing; if MMQ still solves the task, the mechanism is not the one claimed in the theory.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, as formalized in Theorem 4.1, is that the MMQ update of Eq. (6) drives each agent's Q-function close to Q*_i, with error bounded by K*epsilon/(1-gamma), provided d(s'*, ^s'*) <= epsilon. This bound is vacuous unless the estimated set ^S_{s,a_i} contains s'* = f_env(s, a_i, pi*_{-i}(s,a_i)) or a state within epsilon of it. The paper itself states in Section 4.1 that 'we cannot guarantee that s'* in ^S_{s,a_i} subset S_{s,a_i} holds' and defers to a 'performance assessment.' However, the only evidence offered, Figure 5b, measures the percentage of observed true next states falling inside the predicted quantile bounds. In an RO regime, the coordinated optimal joint action is rare or absent from the replay buffer, so the observed transitions used to train the quantile models in Eq. (5) do not imply coverage of the unobserved ideal transition. Including the observed s' in ^S (Algorithm 1, Section 4.3) does not fix this, because s' is generated under the current, possibly suboptimal policies of other agents. Consequently, the max over ^S in Eq. (6) may select a suboptimal next state, and the claimed alignment with ideal transitions is not established. The empirical success might instead stem from negative reward shifting and the double-max structure, which can inject optimism independently of correct s'* coverage. This is a load-bearing gap because the abstract's claim of approaching globally optimal joint behavior rests on the ideal-state inclusion premise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes MaxMax Q-Learning (MMQ), a fully decentralized MARL algorithm meant to mitigate relative over-generalization. For each agent, MMQ learns quantile models of next-state transitions (Eq. (5)), forms a set of candidate next states from the predicted bounds plus the observed next state, draws M samples, and uses the target Y_i(s,a_i)=max over the sampled states of [R_i(s,s')+gamma max_{a'_i} Q_i(s',a'_i)] (Eq. (6)). The authors argue that this max-over-next-states operator approximates ideal transitions assuming other agents play optimally, provide a convergence analysis (Theorems 4.1 and 4.2), and present experiments in differential games, MPE cooperative navigation variants, and Multi-Agent MuJoCo showing that MMQ frequently outperforms I2Q, IDDPG, and HyDDPG.","tokens_in":21441,"tokens_out":7336,"duration_ms":66453,"significance":"The empirical study is a strength: eight seeds with confidence intervals, several RO-prone environments, ablations, and public code. If the theoretical claim were established, MMQ would be an appealing communication-free approach to RO. However, the theoretical core is not currently reliable: the contraction proof has algebraic errors, and the main bound depends on an inclusion assumption that the paper explicitly states cannot be guaranteed and that the experiments do not test. The paper's central explanatory mechanism is therefore not established, although the empirical comparison may still be informative.","major_comments":[{"comment":"The proof of the contraction is not valid as written. In going from Eq. (13) to Eq. (14), the term |R(s,s'_1)-R(s,s'_2)| is dropped without justification, and Eq. (15) bounds a difference of maxima evaluated at different states s'_1 and s'_2 by the sup-norm of Q1-Q2 at a common state; this does not follow from any stated assumption. A correct proof would need a Lipschitz or bounded-reward argument controlling the state difference. Since the contraction property is used to justify convergence to the fixed point Q in the proof of Theorem 4.1, this is a load-bearing gap.","section":"Appendix B, Theorem B.1"},{"comment":"The displayed equality after 'It follows that' is algebraically incorrect: the left side contains R(hat_s'*_t, hat_s'*_{t+1}) - R(hat_s'*_t, s'*_{t+1}), whereas the right side q*(hat_s'*_t, s'*_{t+1}) - q(hat_s'*_t, hat_s'*_{t+1}) contains the opposite reward difference. Hence the bound by K epsilon + gamma Delta_{t+2} is not derived. Moreover, the notation s'*_{t+1} and hat_s'*_{t+1} is introduced without a formal definition connecting these states to the assumption d(s'*, hat_s'*) <= epsilon, so the recursive application of Lemma B.2 is not justified. The theorem's conclusion therefore is not proven.","section":"Appendix B, proof of Theorem 4.1, Eq. (19)"},{"comment":"The premise d(s'*, hat_s'*) <= epsilon is the load-bearing assumption and it is not verified. The paper states on page 6 that 'we cannot guarantee that s'* in hat_S_{s,a_i,t} subset S_{s,a_i} holds'; Theorem 4.1 is vacuous if the estimated set does not contain a state within epsilon of the ideal next state. Figure 5b only reports coverage of observed true next states; under RO the coordinated optimal transition is rare or absent from the replay buffer used in Eq. (5), so this measurement does not address whether the unobserved ideal transition is covered. Algorithm 1's inclusion of the observed s' in hat_S does not fix the issue, because s' is generated under the current, possibly suboptimal, policies of the other agents. The central claim that Eq. (6) aligns each agent's Q-function with the ideal-transition Q* is therefore not established.","section":"Section 4.1 and Theorem 4.1"},{"comment":"The ablation in Figure 6 shows that negative reward shifting has a substantial effect on performance in the differential game, and the theoretical analysis in Theorem 4.1 does not model reward shifting or the double-max structure. It is therefore possible that the observed gains come from the optimistic bias induced by these components rather than from accurate coverage of the ideal next state. An experiment that isolates the ideal-state-selection mechanism, for example by checking whether the argmax over hat_S coincides with the state reached under the joint optimal policy in a small tabular instance, would be needed to support the proposed explanation.","section":"Section 4.3 and Appendix C.1"}],"minor_comments":[{"comment":"The models are called 'non-parametrised quantile models' but they are neural networks with learned parameters; please rephrase to 'neural-network quantile models'.","section":"Section 4.3"},{"comment":"The stated inequality with a linear term in ||a*-a|| is not what is usually called a maximizer of order 2; the terminology and the constants c and delta should be aligned with the cited parametric optimization result.","section":"Appendix B, Assumption A.3"},{"comment":"The theorem statement uses |Q*_i(s,a_i)-Q_i(s,a_i)|, but the proof concludes with |Q*(s_t,a_{i,t})-Q(s_t,hat_a_{i,t})|; the action mismatch needs to be fixed.","section":"Theorem 4.1"},{"comment":"Theorem 4.2 is stated for S=R and hat_S=[-u,u]; this one-dimensional uniform case is a useful sanity check, but the text should not imply it quantifies the general Monte Carlo error without a discussion of how the bound degrades in higher dimensions.","section":"Section 4.2, Theorem 4.2"},{"comment":"The caption 'Percentage of each dim of true next states fall within the predicted quantile bound' has a subject-verb agreement error; it should read 'falls within'.","section":"Figure 5b"}],"recommendation":"major_revision","confidential_remarks":"The empirical comparison may still be publishable if the theory is either repaired or explicitly downgraded to a heuristic motivation, and if the authors add a direct test of ideal-state coverage. I would not recommend rejection at this stage, but the current theoretical claims cannot stand as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"MMQ is a new fully decentralized update rule: each agent learns per-dimension quantile bounds on the next state, samples M candidate states from those bounds plus the observed s', and targets max over candidates of R + gamma max over its own actions. That's a genuine new combination, distinct from I2Q's ideal-transition model and from hysteretic/lenient optimism. The empirical work is solid for a MARL methods paper: eight seeds with CIs, six MPE variants, differential games, and MAMuJoCo, plus ablations on sample count, reward shifting, and quantile vs Gaussian models. Code is public. The results plausibly show that MMQ often beats I2Q, HyDDPG, and IDDPG on the tasks that exhibit relative over-generalization. On that basis the paper deserves a serious referee.\n\nThe soft spots are in the theory, and they are load-bearing for the paper's stated convergence claim. The contraction proof in Appendix B is algebraically invalid as written: Eq. (14) simply drops the reward difference term without justification, so the sup-norm contraction does not follow. Theorem 4.1's proof also has a mismatch: it introduces the best state in the estimated set under the approximate Q, then reasons as if the optimal and approximate next states came from the same transition, which is not established. More important, the central inclusion premise is explicitly disavowed by the authors: Section 4.1 states that they cannot guarantee the ideal next state belongs to the estimated set. The theorem's error bound is a function of the distance between the true best next state and the best in the estimated set, which is small only if that set contains the ideal transition or something close to it. But in an RO regime the coordinated optimal transition may be rare or absent from the replay buffer, so training the quantile models on collected transitions (Eq. 5) does not imply coverage of the ideal transition. Figure 5b checks exactly the wrong thing: it measures whether observed true next states fall inside the predicted bounds, not whether the unobserved coordinated-optimal state does. Negative reward shifting and the double-max structure can inject optimism independently, so the empirical gains do not by themselves validate the inclusion premise.\n\nNone of this makes the paper unserious. The algorithm is clearly specified, the empirical comparison is fair and reasonably thorough, and the method may well be useful as an optimistic heuristic. But the theory currently overclaims. I would send it to peer review with a request for major revision: either fix the contraction and theorem statements, or reframe the theoretical discussion as motivation and add direct evidence that the estimated next-state sets cover or approximate the ideal transition, for example, in a diagnosis environment where the ideal transition can be computed exactly and the distance from the ideal state to the best sampled state is tracked over training. If the inclusion premise turns out to be empirically supported in those settings, the paper would be much stronger.","headline":"MMQ's new combination of quantile-bounded sampling and double-max Bellman targets is empirically promising in RO tasks, but the theory depends on an unverified inclusion premise and needs major revision.","tokens_in":21902,"tokens_out":5731,"would_cite":true,"duration_ms":50272,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces MaxMax Q-Learning (MMQ), a decentralized multi-agent reinforcement learning update rule that counters relative over-generalization by sampling possible next states from quantile-predicted bounds and updating toward…","keywords":["relative over-generalization","decentralized multi-agent reinforcement learning","maxmax Q-learning","quantile models","ideal transitions","cooperative tasks","independent Q-learning","non-stationarity"],"falsifier":"Run an RO task such as the two-agent differential game while deliberately withholding from each agent's replay buffer every transition that moves toward the coordinated optimum; if MMQ still converges to the optimal region, the quantile bounds extrapolate beyond observed ideal transitions, whereas if it stalls as baseline independent learners do, the premise that $\\hat{S}$ contains $s'^*$ is falsified. A quantitative companion check is to compute the distance between $s'^*$ and the nearest sampled candidate in $\\hat{S}$ and verify whether the Q-value gap tracks $(1-\\gamma)^{-1}K\\epsilon$ as Theorem 4.1 predicts.","tokens_in":20830,"feed_emoji":"🎯","tokens_out":9777,"duration_ms":84587,"temperature":0.7,"pith_summary":"Decentralized cooperative agents often settle for actions that look good individually but are jointly suboptimal, a failure called relative over-generalization. This paper claims that a single change to the Q-learning update can remove that failure: after taking its own action, an agent should not update toward the state it actually observed, but toward the most promising next state among the range of states its action could produce while other agents act optimally. The proposed MaxMax Q-Learning (MMQ) predicts that range with two quantile models trained on each agent's own replay buffer, samples candidate next states from it, and applies two maximum operators—one over sampled next states, one over the agent's own next actions. The paper proves that if the best candidate next state is within epsilon of the true ideal next state, the learned Q-values stay within a bounded gap of the optimal joint Q-values, and it shows empirically that MMQ outperforms decentralized baselines across differential games, particle-environment coordination tasks, and multi-agent MuJoCo.","feed_headline":"Two max operators fix multi-agent relative over-generalization","feed_subtitle":"Decentralized agents pick the next state with the highest Q-value, reaching joint optima without a central critic.","key_machinery":"The load-bearing mechanism is the second maximum operator in the Bellman target: the maximum over candidate next states. MMQ replaces the observed next state $s'$ in a standard Bellman update with a sampled set of possible next states $\\hat{S}$, predicted by two non-parametrised quantile networks (at $\\tau=0.05$ and $\\tau=0.95$) plus the observed $s'$ itself, and selects the candidate with the largest value of learned reward plus discounted max-action Q. This selection step is what refines the approximation of ideal transitions: it lets an agent act as if the other agents had chosen the jointly optimal action, without observing their actions. The contraction property of this modified Bellman operator, together with the Lipschitz and order-2-maximizer assumptions used in the appendix, is what carries Theorem 4.1's bound.","core_discovery":"The central claim is that relative over-generalization can be mitigated without centralized training or communication by making each agent's Bellman target optimistic over next states, not just actions. Given the agent's state-action pair $(s, a_i)$, MMQ builds candidate set $\\hat{S} = \\{s'\\} \\cup \\{\\text{samples from } [g^{\\tau_l}_i(s,a_i), g^{\\tau_u}_i(s,a_i)]\\}$, where $g$'s are quantile models of next-state bounds, and updates $Q_i$ toward $Y_i(s,a_i) = \\max_{\\hat{s}'\\in\\hat{S}} \\left[ R_i(s,\\hat{s}') + \\gamma \\max_{a'_i} Q_i(\\hat{s}',a'_i)\\right]$. Because the ideal transition assumes other agents play the optimal joint policy, the true best next state $s'^*$ lies in the full set of possible next states $S_{s,a_i}$; if $\\hat{S}$ contains $s'^*$ (or a state within $\\epsilon$), the max over $\\hat{S}$ recovers the ideal Bellman target. The paper's Theorem 4.1 turns this into a convergence bound: $|Q_i - Q^*_i| \\leq (1-\\gamma)^{-1} K \\epsilon$, and Theorem 4.2 bounds the Monte Carlo sampling error in one dimension by $2u/(M+1)$. Empirically, agents using MMQ reach the optimal cooperative solution in tasks where independent Q-learning, hysteretic, and ideal-transition baselines get stuck.","pith_inferences":["Editorial extension: the paper's coverage check (Figure 5b) measures whether observed transitions fall inside the quantile bounds, but the algorithm's optimism depends on unobserved ideal transitions being covered; a stronger validation would be to compute the distance from $s'^*$ to the sampled candidate set in each RO task and plot it against the Q-value gap predicted by Theorem 4.1.","Editorial extension: if the quantile box is too wide in high dimensions, the Monte Carlo error term grows, so an adaptive proposal distribution—sampling more densely where high Q-values are plausible—could make MMQ scale better than uniform sampling, but that is not tested here.","Editorial extension: in settings where coordinated optimal actions are rare in the replay buffer, MMQ may benefit from an explicit exploration bonus that occasionally forces the coordinated action, because the method's guarantees require evidence of the ideal transition or a bound that contains it."],"forward_implications":["In cooperative tasks with relative over-generalization, agents using MMQ can converge to the globally optimal joint policy using only local transitions, without a centralized critic or explicit communication.","Because the target only needs the range of possible next states, the same update rule applies in deterministic and stochastic environments and in partially observable settings; the paper reports competitive behavior on stochastic differential games and Half-Cheetah 2x3.","If the ideal next state is inside the estimated set, the learned Q-values are exactly those of the ideal-transition Bellman optimality equation, so coordination performance is tied to how well the quantile models cover the true next-state set.","Using more Monte Carlo samples $M$ shrinks the sampling error ($2u/(M+1)$ in one dimension), and the ablation shows learning accelerates with $M$, so the method can trade computation for coordination accuracy."],"supporting_citations":[{"why":"Supplies the ideal-transition formalism and the alignment result that MMQ builds on to approximate optimal joint behavior.","marker":"[Jiang and Lu, 2022]"},{"why":"Hysteretic Q-learning is the optimism-based decentralized baseline that MMQ must outperform and extends.","marker":"[Matignon et al., 2007]"},{"why":"Lenient Q-learning is the other main optimism baseline and the comparison point for handling negative TD errors.","marker":"[Wei and Luke, 2016]"},{"why":"Provides the Monte Carlo optimization technique used to maximize over the sampled next-state set.","marker":"Robert et al. [1999]"},{"why":"Supplies the parametric-optimization result (used as Theorem 6.2) that turns distance between next states into distance between maximizers in the proof of Theorem 4.1.","marker":"[Still, 2018]"},{"why":"Contributes the delayed actor update strategy that MMQ uses to stabilize critic training.","marker":"[Fujimoto et al., 2018]"},{"why":"Contributes negative reward shifting, which MMQ uses to make optimistic next-state selection work.","marker":"[Sun et al., 2022]"}],"fun_headline_variants":["Optimistic next-state max mitigates relative over-generalization","MMQ: sample next states, take max, fix over-generalization","Two max operators fix relative over-generalization","Max over next states, not just actions, fixes relative over-generalization","Optimistic next-state sampling improves coordination without a critic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the set of candidate next states predicted from an agent's own past transitions contains the next state that would occur if the other agents were playing their optimal joint policy, or a state within a small distance of it; if the coordinated optimal transition never appears in the agent's experience, the max over candidates has nothing to select and the convergence bound is vacuous.","fun_headline_variants_meta":{"raw":{"variants":["Optimistic next-state max mitigates relative over-generalization","MMQ: sample next states, take max, fix over-generalization","Two max operators fix relative over-generalization","Max over next states, not just actions, fixes relative over-generalization","Optimistic next-state sampling improves coordination without a critic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001902,"raw_usage":{"total_tokens":7486,"prompt_tokens":1007,"completion_tokens":6479,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":6396}},"tokens_in":623,"tokens_out":6479,"duration_ms":116327,"temperature":1.0,"reasoning_tokens":6396,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:55:10.028308+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an RO task such as the two-agent differential game while deliberately withholding from each agent's replay buffer every transition that moves toward the coordinated optimum; if MMQ still converges to the optimal region, the quantile bounds extrapolate beyond observed ideal transitions, whereas if it stalls as baseline independent learners do, the premise that $\\hat{S}$ contains $s'^*$ is falsified. A quantitative companion check is to compute the distance between $s'^*$ and the nearest sampled candidate in $\\hat{S}$ and verify whether the Q-value gap tracks $(1-\\gamma)^{-1}K\\epsilon$ as Theorem 4.1 predicts.","supporting_citations":[{"cited_title":"I2q: A fully decentralized q-learning algorithm","cited_arxiv_id":null,"evidence_quote":"Supplies the ideal-transition formalism and the alignment result that MMQ builds on to approximate optimal joint behavior."},{"cited_title":"Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams","cited_arxiv_id":null,"evidence_quote":"Hysteretic Q-learning is the optimism-based decentralized baseline that MMQ must outperform and extends."},{"cited_title":"Lenient learning in independent-learner stochastic cooperative games","cited_arxiv_id":null,"evidence_quote":"Lenient Q-learning is the other main optimism baseline and the comparison point for handling negative TD errors."},{"cited_title":"Exploit reward shifting in value-based deep-rl: Optimistic curiosity-based exploration and conservative exploitation via linear reward shaping","cited_arxiv_id":null,"evidence_quote":"Contributes negative reward shifting, which MMQ uses to make optimistic next-state selection work."}],"review_version":1}