{"id":"156721fb-0f5d-48a1-9dc4-970a1792d0bf","arxiv_id":"2412.19873","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Robust Q-FTRL achieves ε-robust CCE in R-contaminated Markov games with H^3 S Σ_i A_i min{H,1/R}/ε^2 samples up to logs, matching a new lower bound; two-player zero-sum gives NE.","lead":"This paper proves that a robust version of the Q-FTRL algorithm learns approximate equilibria in multi-agent robust Markov games with a sample complexity that matches a new information-theoretic lower bound. It is the first minimax-optimal sample-complexity result for this setting, closing gaps left by prior work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof analyzes a synchronous Q-FTRL protocol, but Algorithm 1 as pseudocoded updates agents sequentially within each round; the martingale argument in Lemma 2 does not cover the stated algorithm.","rationale":"The central claim in the reader's strongest_claim is the Theorem 1 sample-complexity upper bound. The weakest point in that proof is the protocol mismatch between the pseudocoded sequential per-agent updates and the synchronous round-k policies used in the analysis. The reader identified exactly this concern, and I agree with it. The concern is load-bearing because if it lands, the paper has not proven its headline sample complexity for the algorithm it actually writes down. It is likely addressable by adjusting the pseudocode to a clear synchronous version or by supplying an asynchronous analysis, which is why I recommend keeping the verdict conditional rather than rejecting. I considered the lower-bound reduction and Corollary 1 issues noted by the reader, but they are secondary relative to the theorem that forms the core claim. The concrete test above would settle whether the proof can be matched to a corrected protocol without changing the rate.","tokens_in":41599,"tokens_out":21188,"duration_ms":235541,"concrete_test":"Check the data-generating process: in a faithful implementation of Algorithm 1 as written, record for each (i,k) which policy version of agent j<i is used when sampling a^k_{j,h}(s,a_i). If it is π^{k+1}_j, then eq. (6) is violated. Analytically, re-derive eq. (53) and the Freedman bound in Lemma 2 under the sequential update order; specifically verify that X_k defined there is conditionally mean-zero with respect to the filtration generated by the asynchronous updates. If the martingale property fails or an extra cross-agent drift term appears, Theorem 1 as stated is unproven. A minimal repair would be to modify Algorithm 1 to a synchronous version (sample for all i using π^k, then update all policies) and re-run the same proof; if the proof goes through unchanged, this confirms the issue is a pseudocode/analysis mismatch rather than a mathematical error in the synchronous algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing mismatch is in Algorithm 1 lines 4–8. For each round k, the loop 'for i=1,...,m' updates π^{k+1}_{i,h} immediately after agent i's Q update. Yet eq. (6) instructs sampling for agent i using a^k_{j,h} ∼ π^k_{j,h} for every j≠i, and the analysis in Section 4 and Appendix A.3 treats round k as having a fixed joint policy (π^k_{1,h},...,π^k_{m,h}) for all agents. In the actual loop order, by the time i=2, agent 1's policy is already π^{k+1}_1, so the samples for agent 2 are drawn under a one-step-ahead policy for agent 1. Consequently, Lemma 2's Freedman argument, which builds a martingale-difference sequence X_k conditional on the history of round-k policies and proves E_{k-1}[X_k]=0, is not a martingale-difference sequence for the data-generating process: the increment for agent i is correlated with the round-k increments of agents updated earlier in the same round. The proof of Theorem 1 therefore verifies a synchronous variant, not the pseudocoded asynchronous algorithm. This is not merely a notational issue: the asynchronous FTRL update evaluates agent i's loss at round k against a mixture that includes opponent policies from different rounds, so the standard FTRL regret lemma (Lemma 8) does not apply as stated. The likely fix is to reorder the pseudocode so all m agents sample using their current policies before any policy is updated, or to add a genuine asynchronous analysis; either way, the theorem statement must be matched to the analyzed protocol.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-horizon multi-player robust Markov games (RMGs) with an R-contamination, agent-wise rectilinear uncertainty set and access to a generative model. It extends Li et al.'s Q-FTRL algorithm to this robust setting and proves that, after KHS∑A_i samples, the returned joint policy is an ε-robust CCE with sample complexity O-tilde(H^3 S ∑ A_i min{H,1/R}/ε^2) for the full range ε∈(0,H] and R∈[0,1). The paper also claims the same complexity for two-player zero-sum RMGs, with an ε-robust NE guarantee for a product-policy output, and proves an information-theoretic lower bound of matching order, yielding minimax optimality. The upper-bound analysis is structured into four steps using robust Bellman decompositions, a variance-based Freedman inequality, and an optimism lemma.","tokens_in":41856,"tokens_out":8397,"duration_ms":82392,"significance":"If the claims hold, the result is a clear advance over prior RMG bounds: it removes the product-of-actions dependence ('curse of multiagency') and the long-horizon/burn-in restrictions, and it matches the lower bound up to logarithmic factors. The paper is transparent about its debts: it imports Lemmas 5 and 8 from Li et al. (2022) and anchors the lower-bound construction to Shi et al. (2024c). The main proof is decomposed into checkable steps with explicit lemmas, and the claimed rate is explicit and falsifiable. However, there are load-bearing correctness gaps: the proof of Theorem 1 analyzes a synchronous protocol that does not match the pseudocoded asynchronous updates; Corollary 1's zero-sum reduction conflates the correlated output analyzed in Section 4 with the product output declared in Algorithm 1; and the lower-bound reduction in Appendix C is asserted rather than derived. These issues are substantial enough that the paper should not be accepted before they are resolved.","major_comments":[{"comment":"The pseudocode updates agents sequentially inside each round: after agent i's update in line 7, agents i+1,...,m sample using the already-updated policy π^{k+1}_{j,h} for j<i. The proof, however, analyzes a synchronous round with a fixed joint policy (π^k_{1,h},...,π^k_{m,h}). In particular, Lemma 2's Freedman argument defines X_k with E_{k-1}[X_k]=0 conditional on the round-k policies, and Lemma 8's FTRL regret bound evaluates agent i's loss at round k against opponent policies π^k_{j,h} for all j≠i. With the pseudocoded asynchronous order, the increment for agent i is correlated with the round-k increments of agents updated earlier in the same round, so the martingale-difference structure and the FTRL regret bound do not apply as stated. Please either reorder the pseudocode so that all agents draw samples and compute Q using the current round-k policies before any policy is updated, or supply a genuine asynchronous analysis; in either case the theorem statement must be matched to the protocol actually analyzed.","section":"§3.1 (Algorithm 1, lines 4–8) and §4.2 (Lemma 2)"},{"comment":"In the zero-sum case the algorithm outputs the product policy π̂1×π̂2 with π̂i = Σ_k α_k π^k_i, whereas the proof of Theorem 1 in Section 4, especially Eqs. (20)–(23), is carried out for the correlated policy π̂ = Σ_k α_k (π^k_1×...×π^k_m). The proof of Corollary 1 applies Theorem 1 to the product output, but the CCE guarantee for the correlated policy does not by itself control the value function under the product policy V^{π̂1×π̂2,R}_{1,1}; the step in Appendix B that uses V^{π̂,R}_{1,1} = -V^{π̂,R}_{2,1} conflates these two objects. Please provide the missing zero-sum reduction (for instance, a bound of the form gapNE(π̂1×π̂2) ≤ C · gapCCE(Σ_k α_k π^k_1×π^k_2) under the robust value functions), or prove Theorem 1 directly for the product output used in the zero-sum case.","section":"§3.1 (lines 12–17) and Appendix B (Corollary 1)"},{"comment":"The lower-bound proof begins by asserting, citing the proof of Theorem 2 in Shi et al. (2024c), that finding a robust NE/CE/CCE of the RMGs degrades to finding the optimal policy of the first agent in a single-agent robust MDP. The rest of Appendix C proves a lower bound for that RMDP, but it does not construct the m-player game or show that any ε-robust CCE of it must identify θ. Since Theorem 2 is the information-theoretic half of the minimax-optimality claim, this reduction needs to be stated and proved explicitly: the construction of the m-player hard instance, the role of the other agents, and the mapping from the CCE gap to the single-agent MDP suboptimality gap should be written out.","section":"Appendix C (Theorem 2)"}],"minor_comments":[{"comment":"The lower bound is displayed as ستيلدO(...), but a lower bound must be stated as Ω(...) or ≳(...); as printed, the display contradicts the surrounding text.","section":"§1.1"},{"comment":"The abstract and Table 1 state R∈[0,1], while Theorem 1 and Corollary 1 require 0≤R<1; please clarify whether R=1 is covered and, if not, correct the range statements consistently.","section":"Abstract and Table 1 vs. Theorem 1"},{"comment":"There are multiple typos and misspellings, e.g., 'smaple complexity', 'compelxity', 'cumulatiev', and a rendering artifact 'f(X) /greaterorsimilar g(X)' in the notation paragraph; a careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious and potentially important extension of Li et al. (2022), and the main upper-bound argument is detailed and largely checkable. The asynchronous-vs-synchronous mismatch and the zero-sum output mismatch are local in the sense that a synchronous rewrite of Algorithm 1 and a proper zero-sum reduction would likely make the claims true; I therefore do not recommend rejection. The lower-bound reduction in Appendix C, however, needs more than copyediting and should be verified carefully. I also suggest checking the positioning with respect to Shi et al. (2024a,c), since the claimed first-minimax-optimal statement depends on the precise uncertainty-set and equilibrium definitions used there."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: I think this paper has the right main result, and the core analysis is worth taking seriously, but it currently proves a slightly different algorithm than the one it pseudocodes. That is a fixable mismatch, not a fatal flaw.\n\nWhat's new: first minimax-optimal sample complexity for RMGs under R-contamination with a generative model: H^3 S ∑ A_i min{H,1/R}/ε^2 for robust CCE, with a matching lower bound up to log factors. It removes the product-of-actions dependence, the burn-in cost, and the ε/R restrictions from Shi et al. and Ma et al. The robust Bellman operator, the bonus term, and the hard-instance lower bound require genuinely new work. The proof structure is clean: decompose the CCE gap into four terms and bound each with Freedman and a variance telescope. The authors cite prior work appropriately; the two imported lemmas from Li et al. (2022) are technical and standard.\n\nThe load-bearing soft spot is the algorithm/proof mismatch. Algorithm 1 lines 4–8 update agents sequentially inside each round, so by the time agent i>1 is updated, earlier agents' policies are already at round k+1. But eq. (6) and the martingale argument in Lemma 2/A.3 condition on all opponents using round-k policies. Lemma 2's X_k is then not mean-zero conditional on the actual data-generating history, and the standard FTRL regret lemma (Lemma 8) does not apply to the asynchronous sequence. This is not a mere notation issue; the theorem as written covers a synchronous variant. The fix is straightforward: rewrite the pseudocode so all agents draw samples under their round-k policies before any policy is updated, or add a genuine asynchronous analysis. Either way, the theorem statement needs to match what is proved.\n\nTwo smaller points. Corollary 1's NE claim is a terse reduction: it shows the correlated output has 2ε gap for the product policy, then rescales. That is plausible and likely correct, but a referee should ask for the gap to be spelled out. The lower bound imports the RMG-to-RMDP reduction from Shi et al. (2024c); this is legitimate use of a cited result, but it should be checked against this paper's exact definitions.\n\nBottom line: the main result is real and important for the subfield, and the analysis is mostly rigorous. The mismatch is embarrassing but easy to repair. Send it to a serious referee; the likely outcome is minor-to-moderate revision.","headline":"A genuine minimax-optimal sample bound for robust Markov games, but the proof as written analyzes a synchronous algorithm while the pseudocode is asynchronous; the gap is easy to close and the paper deserves a serious referee.","tokens_in":42494,"tokens_out":3584,"would_cite":true,"duration_ms":373453,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Robust multi-agent RL improves to minimax-optimal sample complexity","keywords":["robust Markov games","multi-agent reinforcement learning","sample complexity","coarse correlated equilibrium","Nash equilibrium","Q-FTRL","R-contamination","generative model"],"falsifier":"Implement Algorithm 1 exactly as pseudocoded (lines 4–8 updating agents one by one within a round) on a small two-agent, two-state, three-horizon game with $R=0.5$ and the $K$ prescribed by (15); if the empirical gapCCE does not reach $\\varepsilon$ at the predicted $K$, or if the martingale-like claim of Lemma 2 fails when $j\\neq i$ samples use policies updated earlier in the same round, the synchronous-analysis gap is confirmed. As a second check, setting $R=0$ should recover the standard minimax rate $H^4S\\sum_i A_i/\\varepsilon^2$; a deviation by a factor of $H$ would falsify the claimed dependence.","tokens_in":2192,"feed_emoji":"🎮","tokens_out":2438,"duration_ms":93282,"temperature":0.7,"pith_summary":"This paper asks how many samples from a simulator are necessary and sufficient for several agents to find an approximately robust equilibrium in a finite-horizon Markov game when the transition law is only known to lie in an R-contamination set around a nominal kernel. The authors extend the Q-FTRL algorithm, previously minimax-optimal for ordinary Markov games, to this robust setting, and prove that $KHS\\sum_{i=1}^m A_i$ samples — with $K$ set by $\\widetilde O(H^3S\\sum_{i=1}^m A_i \\min\\{H,1/R\\}/\\varepsilon^2)$ — suffice to output an $\\varepsilon$-robust coarse correlated equilibrium for any $\\varepsilon\\in(0,H]$ and $R\\in[0,1]$. They further prove a matching information-theoretic lower bound, so the rate is minimax optimal up to log factors; in the two-player zero-sum case the same algorithm yields an $\\varepsilon$-robust Nash equilibrium. The result matters because earlier algorithms either tolerated only tiny uncertainty, paid a factor exponential in the number of agents, or incurred a long-horizon burn-in cost; this work removes all three limitations at once.","feed_headline":"Robust multi-agent RL hits minimax-optimal sample bounds","feed_subtitle":"Matches lower bound; removes the classic action-curse and long-horizon barriers.","key_machinery":"The machinery is Q-FTRL (Follow-the-Regularized-Leader) lifted to robust Markov games. At each horizon step $h$, for $k=1,\\dots,K$, each agent $i$ samples $K$ next states from the nominal kernel for every $(s,a_i)$ pair, forms the empirical robust target $q^k_{i,h} = r^k_{i,h} + (1-R)P^k_{i,h}\\hat V_{i,h+1} + R\\min \\hat V_{i,h+1}$, updates $Q^k_{i,h}$ by the convex average $(1-\\alpha_k)Q^{k-1} + \\alpha_k q^k$, and sets $\\pi^{k+1}_{i,h}(\\cdot|s) \\propto \\exp(\\eta_{k+1} Q^k_{i,h}(s,\\cdot))$. The output policy is the weighted average over rounds. Two pieces carry the proof: the variance-aware bonus $\\beta_{i,h} = O(\\sqrt{(\\log^3(KS\\sum_{i=1}^m A_i/\\delta)/K)\\min\\{H,1/R\\}})$ added to the value estimate, and the robust Bellman identity that pins the worst-case kernel to the point mass at the minimum of the next value function. Freedman's inequality then controls the martingale sequence formed by the sampling noise, and the bonus guarantees optimism (Lemma 4), so the gap decomposition in equation (32) telescopes to the claimed rate.","core_discovery":"Under agent-wise $(s,a)$-rectangularity, the $R$-contamination model makes the worst-case transition an explicit convex combination: the robust Bellman update is $Q_{i,h}^{\\pi,R}(s,a) = r_{i,h}(s,a) + (1-R)P^0_{h,s,a}V_{i,h+1}^{\\pi,R} + R\\min V_{i,h+1}^{\\pi,R}$. The paper shows that optimistic Q-FTRL — where each agent maintains $Q^k$ via an online average of these robust targets and updates its policy with an exponential-weight rule — returns a joint policy whose robust equilibrium gap is at most $\\varepsilon$ with probability at least $1-\\delta$ once $KHS\\sum_{i=1}^m A_i \\geq C H^3S\\sum_{i=1}^m A_i \\min\\{H,1/R\\}\\log^3(KS\\sum_{i=1}^m A_i/\\delta)/\\varepsilon^2$. This is proven by decomposing the gap into four terms and bounding each; the lower bound (Theorem 2) constructs a family of robust MDPs inside which learning a robust CCE is as hard as identifying a code word, giving the same rate up to log factors. The paper's central claim is that this is the first minimax-optimal sample complexity for robust Markov games under the generative model.","pith_inferences":["If the additive-actions rate is correct, robust CCE learning under a generative model stays tractable as the number of agents grows, so robustness need not re-introduce the multiagency curse for equilibrium computation.","The $\\min\\{H,1/R\\}$ factor suggests the effective horizon of a robust game is $\\min\\{H,1/R\\}$; an implicit, testable prediction is that other uncertainty sets (e.g., total variation or KL balls) reproduce the same factor, as the authors conjecture.","A reader attempting to reproduce Theorem 1 should either implement the synchronous version of Algorithm 1 or extend the analysis to asynchronous updates; this is the point most likely to need repair.","The lower bound reduces robust CCE to robust MDP identification, so the same hard-instance construction plausibly yields minimax lower bounds for robust correlated equilibria and other equilibrium notions."],"forward_implications":["For any fixed number of agents, the sample complexity is additive in the agents' action counts, so the curse of multiagency (the product-of-actions factor) is broken for robust CCE.","The bound is valid for the full accuracy range $\\varepsilon\\in(0,H]$ and uncertainty level $R\\in[0,1]$, meaning the algorithm needs no burn-in cost before it starts improving.","In two-player zero-sum robust games, the same sample count buys an $\\varepsilon$-robust Nash equilibrium, not just a correlated one.","The matching lower bound means no other algorithm using a generative model can do better in the worst case up to log factors, settling the minimax rate for $R$-contamination robust Markov games.","The $\\min\\{H,1/R\\}$ factor shows the intrinsic cost of robustness: uncertainty level $R$ becomes as expensive as horizon $H$ once $R \\gtrsim 1/H$."],"supporting_citations":[{"why":"Supplies the Q-FTRL algorithm, its regret lemma, and the minimax-optimal sample complexity for standard Markov games that this paper extends to the robust setting.","marker":"(Li et al., 2022)"},{"why":"Provides the robust NE sample complexity with the product-of-actions curse and the hard-instance construction of Theorem 2 that the lower-bound proof follows.","marker":"(Shi et al., 2024c)"},{"why":"Achieves robust CCE with additive action dependence but a burn-in cost and worse $\\varepsilon$-dependence; the rate this paper improves upon.","marker":"(Shi et al., 2024a)"},{"why":"Gives a robust CE algorithm valid only for tiny uncertainty $R\\leq\\varepsilon/(SH^2)$; the restrictive-range baseline this work removes.","marker":"(Ma et al., 2023)"},{"why":"Proves existence of robust NE under general uncertainty sets and gives a product-of-actions algorithm; also supplies the robust best-response fact used in Section 2.","marker":"(Blanchet et al., 2024)"},{"why":"Defines the $R$-contamination model from which the uncertainty set in (1) is built.","marker":"(Huber, 1965)"},{"why":"Gilbert–Varshamov lemma constructs the packing $\\Theta$ of hard-instance codes with Hamming distance $H/8$ used in the lower bound.","marker":"(Gilbert, 1952)"},{"why":"Fano's inequality converts KL divergences between nominal kernels into the information-theoretic lower bound.","marker":"(Tsybakov, 2009)"}],"fun_headline_variants":["Minimax-optimal robust RL for multi-agent games","Robust Markov games: first minimax-optimal sample bound","Closing the sample-complexity gap in robust multi-agent RL","Optimal sample complexity for robust multi-agent RL","Minimax-optimal robust equilibrium learning"],"cache_read_input_tokens":44416,"weakest_assumption_plain":"The proof requires that the policies used to draw samples at round $k$ are exactly the round-$k$ policies whose updates are being analyzed; the pseudocode's sequential update of agents inside each round conflicts with this, so the proof as written covers a synchronous implementation and may not cover the asynchronous one.","fun_headline_variants_meta":{"raw":{"variants":["Minimax-optimal robust RL for multi-agent games","Robust Markov games: first minimax-optimal sample bound","Closing the sample-complexity gap in robust multi-agent RL","Optimal sample complexity for robust multi-agent RL","Minimax-optimal robust equilibrium learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000593,"raw_usage":{"total_tokens":2853,"prompt_tokens":1097,"completion_tokens":1756,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":713,"completion_tokens_details":{"reasoning_tokens":1678}},"tokens_in":713,"tokens_out":1756,"duration_ms":11452,"temperature":1.0,"reasoning_tokens":1678,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:56:35.014415+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 1 exactly as pseudocoded (lines 4–8 updating agents one by one within a round) on a small two-agent, two-state, three-horizon game with $R=0.5$ and the $K$ prescribed by (15); if the empirical gapCCE does not reach $\\varepsilon$ at the predicted $K$, or if the martingale-like claim of Lemma 2 fails when $j\\neq i$ samples use policies updated earlier in the same round, the synchronous-analysis gap is confirmed. As a second check, setting $R=0$ should recover the standard minimax rate $H^4S\\sum_i A_i/\\varepsilon^2$; a deviation by a factor of $H$ would falsify the claimed dependence.","supporting_citations":[],"review_version":1}