REVIEW 3 major objections 3 minor 17 references
Minimax-Optimal Multi-Agent Robust Reinforcement Learning
T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Robust multi-agent RL improves to minimax-optimal sample complexity
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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$.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§3.1 (Algorithm 1, lines 4–8) and §4.2 (Lemma 2)] 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.
- [§3.1 (lines 12–17) and Appendix B (Corollary 1)] 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.
- [Appendix C (Theorem 2)] 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.
minor comments (3)
- [§1.1] The lower bound is displayed as ستيلدO(...), but a lower bound must be stated as Ω(...) or ≳(...); as printed, the display contradicts the surrounding text.
- [Abstract and Table 1 vs. Theorem 1] 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.
- [Throughout] 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.
Circularity Check
No circularity: the robust CCE bound is derived from robust-specific lemmas, with only standard FTRL/Freedman tools imported from prior work.
full rationale
The paper's central claim—the minimax-optimal sample complexity of Algorithm 1 for robust Markov games—is not circular. Theorem 1 is proved by a four-step decomposition in Section 4: the robust value-function errors are bounded in Lemma 2 via a Freedman martingale argument adapted to the R-contamination contraction, the bonus/variance term is controlled in Lemma 3, and optimism is established in Lemma 4 using the Q-FTRL regret bound of Lemma 8. The robust-specific parts (Lemmas 1, 2, 3, 4, 6) are proved in the appendix from the robust Bellman equation and the R-contamination uncertainty set; they do not assume the theorem's conclusion. The imports from Li et al. (2022) are standard technical tools—step-size properties (Lemma 5), Freedman's inequality (Lemma 7), and an FTRL regret bound (Lemma 8)—with stated assumptions that do not include robust CCE; although one author overlaps, these are prior external lemmas rather than a conclusion smuggled in by self-citation. The lower bound in Theorem 2 is anchored to hard instances constructed following Shi et al. (2024c), which is not the present paper's own result and is not derived from the upper bound. There is no fitted parameter renamed as a prediction, no quantity defined in terms of the target, and no known result merely renamed under new coordinates. The reader-flagged mismatch between Algorithm 1's sequential in-round update and the analysis's synchronous round-k policies is a potential correctness or implementation gap, but it is not circularity: even if the proof covers a slightly different protocol, the claimed theorem does not reduce by definition to its inputs. Accordingly, the appropriate finding is no significant circularity.
Assumptions & free parameters
assumptions (6)
- standard math Freedman's inequality for martingale concentration (Lemma 7)
- standard math FTRL regret bound for exponential-weight updates (Lemma 8, adapted from Theorem 3 of Li et al. 2022)
- domain assumption R-contamination uncertainty set with agent-wise (s,a)-rectangularity (eq. 1)
- domain assumption Generative model returns independent next-state samples from the nominal kernel for any queried (s,a) at any step h
- standard math Fano's inequality and Gilbert-Varshamov packing bound |Θ| ≥ e^{H/8}
- ad hoc to paper RMG lower bound reduces to robust MDP lower bound following Shi et al. (2024c)
Cite this review
Pith. "Pith review of Minimax-Optimal Multi-Agent Robust Reinforcement Learning." pith.science (2026). https://pith.science/paper/ZOMOHONR
@misc{pith2026241219873,
author = {Pith},
title = {Pith review of: Minimax-Optimal Multi-Agent Robust Reinforcement Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZOMOHONR}},
note = {Machine review of arXiv:2412.19873}
}
abstract
Multi-agent robust reinforcement learning, also known as multi-player robust Markov games (RMGs), is a crucial framework for modeling competitive interactions under environmental uncertainties, with wide applications in multi-agent systems. However, existing results on sample complexity in RMGs suffer from at least one of three obstacles: restrictive range of uncertainty level or accuracy, the curse of multiple agents, and the barrier of long horizons, all of which cause existing results to significantly exceed the information-theoretic lower bound. To close this gap, we extend the Q-FTRL algorithm \citep{li2022minimax} to the RMGs in finite-horizon setting, assuming access to a generative model. We prove that the proposed algorithm achieves an $\varepsilon$-robust coarse correlated equilibrium (CCE) with a sample complexity (up to log factors) of $\widetilde{O}\left(H^3S\sum_{i=1}^mA_i\min\left\{H,1/R\right\}/\varepsilon^2\right)$, where $S$ denotes the number of states, $A_i$ is the number of actions of the $i$-th agent, $H$ is the finite horizon length, and $R$ is uncertainty level. We also show that this sample compelxity is minimax optimal by combining an information-theoretic lower bound. Additionally, in the special case of two-player zero-sum RMGs, the algorithm achieves an $\varepsilon$-robust Nash equilibrium (NE) with the same sample complexity.
Reference graph
Works this paper leans on
-
[9]
Minimax-opti mal multi-agent rl in markov games with a generative model
Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-opti mal multi-agent rl in markov games with a generative model. arXiv preprint arXiv:2208.10458 ,
-
[10]
Markov games as a framework for multi-age nt reinforcement learning
Michael L Littman. Markov games as a framework for multi-age nt reinforcement learning. In Machine learning proceedings 1994, pp. 157–163. Elsevier,
work page 1994
-
[12]
Ziang Song, Song Mei, and Yu Bai. When can we learn general-su m markov games with a large number of players sample-efficiently? arXiv preprint arXiv:2110.04184 ,
-
[14]
Robust markov decision processes without model estimation
Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M Jordan, and Zh ihua Zhang. Robust markov decision processes without model estimation. arXiv preprint arXiv:2302.01248 ,
-
[15]
o(t−1) convergence of optimistic-follow-the-regularized-lead er in two-player zero-sum markov games
Yuepeng Yang and Cong Ma. o(t−1) convergence of optimistic-follow-the-regularized-lead er in two-player zero-sum markov games. arXiv preprint arXiv:2209.12430 ,
-
[16]
Sustainbench: Ben chmarks for monitoring the sustainable development goals with machine learning
Christopher Yeh, Chenlin Meng, Sherrie Wang, Anne Driscoll , Erik Rozi, Patrick Liu, Jihyeon Lee, Marshall Burke, David B Lobell, and Stefano Ermon. Sustainbench: Ben chmarks for monitoring the sustainable development goals with machine learning. arXiv preprint arXiv:2111.04724 ,
-
[17]
arXiv preprint arXiv:2010.09776 ,
arXiv 2010
-
[1952]
URL https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1952.tb01393.x
doi: https://doi.org/10.1002/j.1 538-7305.1952.tb01393.x. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1952.tb01393.x. Vineet Goyal and Julien Grand-Clement. Robust markov decis ion processes: Beyond rectangularity. Math- ematics of Operations Research , 48(1):203–226,
Show all 17 references
-
[1953]
Breaking the curse of multiagency in robust multi-agent reinforcement learning
Laixi Shi, Jingchu Gai, Eric Mazumdar, Yuejie Chi, and Adam W ierman. Breaking the curse of multiagency in robust multi-agent reinforcement learning. arXiv preprint arXiv:2409.20067 , 2024a. Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, an d Yuejie Chi. The curiou...
-
[1998]
Openspiel: A framework for reinforcement learning in games
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vin icius Zambaldi, Satyaki Upadhyay, Julien Péro- lat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shaye gan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09453 ,
1908 arXiv
-
[2005]
Feature-based q-learn ing for two-player stochastic games
Zeyu Jia, Lin F Yang, and Mengdi Wang. Feature-based q-learn ing for two-player stochastic games. arXiv preprint arXiv:1906.00423,
1906 arXiv
-
[2010]
Model-base d reinforcement learning is minimax-optimal for offline zero-sum markov games
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. Model-base d reinforcement learning is minimax-optimal for offline zero-sum markov games. arXiv preprint arXiv:2206.04044 , 5:21,
-
[2018]
V-lear ning–a simple, efficient, decentralized algorithm for multiagent rl
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-lear ning–a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555 ,
-
[2020]
Deepracer: Educa tional autonomous racing platform for experimentation with sim2real reinforcement learning
Bharathan Balaji, Sunil Mallya, Sahika Genc, Saurabh Gupta , Leo Dirac, Vineet Khare, Gourav Roy, Tao Sun, Yunzhe Tao, Brian Townsend, et al. Deepracer: Educa tional autonomous racing platform for experimentation with sim2real reinforcement learning. arXiv preprint arXiv:1911.01562 ,
1911 arXiv
-
[2021]
Smart-llm: Smart multi-agent robot task planning using large language models
Shyam Sundar Kannan, Vishnunandan LN Venkatesh, and Byung- Cheol Min. Smart-llm: Smart multi-agent robot task planning using large language models. arXiv preprint arXiv:2309.10062 ,
-
[2022]
Fast bell man updates for robust mdps
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Fast bell man updates for robust mdps. In Interna- tional Conference on Machine Learning , pp. 1979–1988. PMLR,
1979
-
[2023]
What is the solution for state-adversarial multi-agent reinforcemen t learning? arXiv preprint arXiv:2212.02705 ,
Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, S haofeng Zou, and Fei Miao. What is the solution for state-adversarial multi-agent reinforcemen t learning? arXiv preprint arXiv:2212.02705 ,
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.