acceptodds
Under review as a conference paper at ICLR 2027

Minimax-Optimal Multi-Agent Robust Reinforcement Learning

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 typically suffer from the curse of multiple agents, where the complexity scales exponentially with the number of players. The Follow-the-Regularized-Leader (FTRL) framework has emerged as a powerful technique for addressing this issue in standard Markov games (MGs). However, its application to RMGs remains suboptimal, as the resulting complexity has significantly worse dependence on both the horizon and the accuracy compared to prior works. To address these challenges, we study the problem in the finite-horizon setting, assuming an -contamination uncertainty set and access to a generative model. We prove that applying FTRL in this setting achieves an -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 denotes the number of states, is the number of actions of the -th agent, and is uncertainty level. Furthermore, we establish a matching information-theoretic lower bound under the same uncertainty model, thereby proving the minimax optimality of our result. To the best of our knowledge, this is the first work that achieves minimax-optimal sample complexity in the setting of RMGs.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, multi-agent, robust game, sample complexity, minimax

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_QF1sOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this work, the authors study the computational limitations of sample-based algorithms for multi-agent reinforcement learning (MARL). Under assumptions similar to those commonly adopted in the existing literature, the paper proposes an algorithm that achieves an improved complexity–accuracy tradeoff by relaxing the approximation error bound by a quadratic factor. The resulting approach reduces the computational complexity required to obtain an approximately optimal solution while maintaining theoretical performance guarantees.

Critical strengths

-Quadratic improvement on an H/εH/\varepsilon factor is provided for the required sample complexity. -The paper seems to have an extensive bibliography on the topic.

Critical weaknesses
  • By scaling the reward/cost function, one can define an equivalent problem in which the desired error rate can be chosen as arbitrarily, as long as the error rate is available over an interval of the form [0, a] for some “a”. In particular, the result of Shi et al. (2024a) can be extended to [0, H] by shrinking the objective function, then applying the available result on the full interval, and then removing the scaling. Thus, the improvement on the burn in cost does not seem to be a significant improvement at all.
  • The present sample complexity is close to the optimal one, as argued in this work. However, the arguments employed to achieve this improved rate seem rather standard.
Questions for authors

-I am certain that the result of Shi et al. (2024) can be expanded to the whole interval presented in this work using the technique that I mentioned above. Is there any inherent advantage of having error rate available on the whole interval [0, H]? -What are the main technical advancements made in the current manuscript compared to previous work?

3 comments

We sincerely thank the reviewer for the careful reading. Our point-by-point response is as follows.

Reward scaling does not work. Reward scaling cannot extend the stated sample complexity guarantee to the full accuracy range. The key observation is that both the admissible accuracy range and the full value range change proportionally in different reward scales, leaving their ratio unchanged (see detailed explanation below). If we have misunderstood the proposed argument, could you please clarify how scaling and rescaling work?

Specifically, for rewards in [0,1][0,1], Shi et al. (2024a) establish the following sample complexity bound, up to log factors: H6S∑iAiε4min⁡H,1R,0<ε≤min⁡H,1R.\frac{H^6S\sum_iA_i}{\varepsilon^4}\min\\{H,\frac{1}{R}\\},\qquad 0<\varepsilon\le \sqrt{\min\\{H,\frac{1}{R}\\}}. Scaling rewards by ρ>0\rho>0 changes the full value range from [0,H][0,H] to [0,ρH][0,\rho H] and expresses the same guarantee as

\qquad 0<\varepsilon'\le\rho \sqrt{\min\\{H,\frac{1}{R}\\}}.$$ To obtain accuracy $\varepsilon$ in the original problem, the scaled problem must be solved to accuracy $\varepsilon'=\rho\varepsilon$. Removing the scaling therefore gives $$\frac{\rho^4H^6S\sum_iA_i}{(\rho\varepsilon)^4}\min\\{H,\frac{1}{R}\\} = \frac{H^6S\sum_iA_i}{\varepsilon^4}\min\\{H,\frac{1}{R}\\}, \qquad 0<\varepsilon\le\frac{1}{\rho} \rho \sqrt{\min\\{H,\frac{1}{R}\\}}=\sqrt{\min\\{H,\frac{1}{R}\\}}.$$ This recovers the original guarantee. The admissible accuracy range covers the same fraction $\rho \sqrt{\min\\{H,1/R\\}}/(\rho H)=\sqrt{\min\\{H,1/R\\}}/H$ of the full value range. Prior literature also shows that full-range sample optimality is nontrivial. [R1-R3] establish it in generative model, online, and offline single-agent RL, respectively, improving [R5-R7], whose sample optimality holds only over restricted accuracy ranges. See Table 1 and Section 3.3 of [R1], Table 1 and Section 1.1 of [R2], and Table 1 and the discussion titled ``Full $\varepsilon$-range and no burn-in cost'' following Theorem 4 in [R3]. Similarly, [R4] highlights full-range minimax optimality in finite-horizon MARL, whereas [R8] requires a restrictive accuracy range in discounted games. Despite the different horizon formulations, they further demonstrate that full-range guarantees are a recognized consideration in MARL theory. We have discussed this in Section 3.2 (line 417-423) and Appendix (line 1130-1145). **Advantages of full range optimal.** Achieving minimax sample complexity throughout $\varepsilon\in(0,H]$ provides optimal error guarantees across sample sizes, without an additional burn-in requirement. As discussed in our response to your previous comment, eliminating such requirements has received considerable attention. In addition, beyond removing burn-in cost, our main contribution is to establish minimax sample complexity for robust MARL under the R-contamination model. **Technical advancements.** Thank you for your question. It is challenging to establish minimax sample complexity for robust MARL. We clarify the key technical differences through comparisons with Shi et al. (2024a,c), the most closely related works. Shi et al. (2024a) use $N=\Omega(H^2\min\\{H,1/R\\}\varepsilon^{-2})$ samples per state--individual-action pair in each iteration, whereas we use only one. Our analysis must therefore control the weighted cumulative estimation error without accurate transition estimates at each iteration. We also reduce the number of iterations $K$ in each stage $h$ by a factor of $H/\min\\{H,1/R\\}$, which requires refined control of the span and variance of $\widehat{V}_{i,h}$. This is nontrivial because the bounds for $\widehat{V}_{i,h}$, $\beta_{i,h}$ and $q_{i,h,s}^k$ must be established jointly. Shi et al. (2024c) estimate $Q$-functions over the joint action space. Our approach instead uses estimates indexed by individual actions and avoids explicitly solving for equilibria at each stage. This yields a dependence on $\sum_i A_i$ rather than $\prod_i A_i$. We have highlighted these technical steps and their differences from prior analyses in Section 3.2 (line 425-431). [R1] Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model. NeurIPS 2020 [R2] Settling the Sample Complexity of Online Reinforcement Learning. COLT 2024 [R3] Settling the Sample Complexity of Model-Based Offline Reinforcement Learning. AoS 2024 [R4] Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model. NeurIPS 2022 [R5] Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal. COLT 2020 [R6] UCB momentum Q-learning: Correcting the bias without forgetting. ICML 2021 [R7] Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. ICML 2022 [R8] Model-based reinforcement learning with a generative model is minimax optimal. COLT 2020

I thank the authors for their detailed responses. Some further comments:

An argument for an improved burn-in region: The authors have to apply the result to the reward function r′ = ρr when ε is greater than the given threshold but ρε is within the feasible threshold. Then, just use the fact that the desired gap obtained under r′ is just that of r but obtained under the factor ρ.

A sketch of the argument would be as follows. If r is the reward function, let ρ be a positive number and let r′ := ρr. Then, by Gap(r), denote the gap between the learned policy and the equilibrium. We have Gap(r′) = ρGap(r). For ε′ = ρε, when ε′ ≤√(min(H, 1/R) and ε >√︁(min(H, 1/R), from Shi et al., we obtain N = Õ (H6S (Σ︂i Ai) min(H, 1/R)/(ε′)4) for ρ Gap(r) by applying the result to Gap(r′). Such a ρ always exists. In fact, since we can take ρ ≤ 1, we have ρ∗(ε) = min (︃1, (1/ε)√min(H,1/R))︃ as the optimal factor ρ. For all 0 < ε < H, we then should obtain Õ (H6S (Σ︂i Ai) min(H, 1/R)/ min(ε,√︁min(H, 1/R))4).

However, it seems that when we have low uncertainty and a small horizon length, this approach leads to a worse asymptotic bound than the original result of Shi et. al. in the extended range. Since this trick gives relatively worse results in certain regimes, I am convinced that the authors had a non-trivial addendum (in that case, we have a factor of H7 inside Õ).

Updated assessment: Hoping that the authors will further update the paper in view of the above comments, and given the responses they have provided to the other earlier comments, I have updated my score to “weak accept”.

Thank you for your follow-up and for raising your score. We have revised the manuscript to clarify that the resulting sample complexity bound obtained by rescaling has a worse dependency in the extended range.

Reviewer_a78dOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the sample complexity of multi-agent robust reinforcement learning. For an mm-player finite-horizon robust Markov game with horizon HH, state space size SS, action space size AiA_i for the ii-th player, and uncertainty level RR, the authors establish a sample complexity upper bound of O~(SH3∑i=1mAiε2min⁡{H,1R})\widetilde{O}\left(\frac{SH^3\sum_{i=1}^m A_i}{\varepsilon^2}\min\{H,\frac{1}{R}\}\right) for achieving an ε\varepsilon-robust coarse correlated equilibrium (CCE), where ε∈(0,H]\varepsilon\in(0,H]. This result improves upon existing results in three key aspects: (i) improving the dependence on the horizon HH, (ii) overcoming the curse of multi-agency, and (iii) eliminating the burn-in cost by establishing guarantees for the full range of target accuracy ε\varepsilon. Furthermore, under the considered R-contamination uncertainty model, the authors establish an information-theoretic lower bound that matches the upper bound up to logarithmic factors and the dependence on the number of agents. Together, these results establish the first minimax-optimal sample complexity guarantee for multi-agent robust reinforcement learning.

Critical strengths

Robust multi-agent reinforcement learning is an important research direction that has attracted increasing attention in recent years. Despite substantial theoretical progress, establishing minimax-optimal sample complexity guarantees remains a challenging open problem due to the complexity of the multi-agent robust setting. Achieving such guarantees requires simultaneously addressing several fundamental challenges, including the curse of multi-agency, the additional complexity introduced by handling uncertainty sets, and the potentially suboptimal dependence on key problem parameters such as the HH and ε\varepsilon.

This paper makes significant progress toward resolving these challenges. To the best of my knowledge, this is the first result to achieve the minimax-optimal sample complexity in the robust Markov game.

In my opinion, this work makes a significant theoretical contribution to multi-agent robust reinforcement learning and is worthy of publication.

Critical weaknesses
  1. This work focuses on the R-contamination uncertainty model. It would be valuable to extend the theoretical guarantees to other uncertainty sets, such as those defined by total variation or KL divergence. Such extensions could be considered in future work.
  2. The proposed algorithm assumes access to a generative model, which allows independent sampling from arbitrary state-action pairs. It would be interesting to extend the results to more general data collection settings, such as online reinforcement learning, where data are collected sequentially through interactions with the environment.
Questions for authors
  1. Could the authors comment on whether the proposed FTRL framework can be extended to other commonly used uncertainty sets, such as those defined by total variation or KL divergence?
  2. The proposed algorithm introduces an optimistic bonus term in the value function estimation (see (12)). Could the authors explain how the R-contamination uncertainty model influences the design of this bonus compared with standard Markov games?
  3. The upper bound in Theorem 1 holds for all R∈[0,1]R\in[0,1], whereas the lower bound in Theorem 2 is established only for R∈[0,cR]R\in[0,c_R], where cR<1c_R<1 is a constant. Is it possible to establish a matching lower bound when RR is 1?
1 comment

We sincerely thank the reviewer for the positive assessment and for recognizing the significance of our work. Our point-by-point response is as below.

Uncertainty model. Thank you for your question. Other uncertainty sets, such as those based on TV distance or KL divergence, induce different robust Bellman operators, and the dependence on the uncertainty level may differ from the min⁡H,1/R\min\\{H,1/R\\} factor in our analysis. A possible extension is to incorporate their robust Bellman operator through dual formulations, and adapt the bonus terms and learning rates to the resulting estimation errors and value spans. Extending the theoretical guarantees would require controlling the statistical errors in these robust Bellman updates and their propagation across stages. We have discussed this extension in Section 5 (line 516-518) and left it as an important direction for future work.

Online setting. Thank you for your suggestion. Extending our results to the online setting requires substantial modifications beyond the current simulator-based framework. In particular, exploration mechanisms such as UCB techniques are needed. Moreover, unlike the generative model setting, the online setting does not provide accurate estimates of the value functions from previous layers, leading to potentially larger estimation errors for Vi,h+1V_{i,h+1} and making the analysis more challenging. We have added a discussion in Section 5 (line 520-522) of the revised manuscript and left this as a future work.

Bonus term. Thank you for your question. The bonus term is designed to control the variance arising in the robust Bellman updates, which depends on the span of the next-stage value estimate. Under the RR-contamination model, we establish that the span of V^i,h+1\widehat{V}_{i,h+1} is of order min⁡H,1/R\min\\{H,1/R\\}, rather than the general bound of order HH used in standard MARL. This sharper span bound allows us to choose the bonus based on min⁡H,1/R\min\\{H,1/R\\}, which appears both in the denominator of the square-root prefactor and as the additive term inside the weighted sum defining βi,h\beta_{i,h}. We have explained this in Section 3.1 (line 342-343) of the revised manuscript.

Range of RR. Indeed, our lower bound does not cover the regime cR<R≤1c_R< R\leq 1, where cRc_R is arbitrarily close to 11. However, this regime is of limited practical interest, as the simulator becomes nearly inaccurate when RR approaches 11. We have explained this in Section 3.2 (line 398-400) of the revised manuscript.

Reviewer_R9K4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies multi-agent robust games under R-contamination uncertainty. The authors provide tighter upper and lower bounds, achieving minimax-optimal results. Compared with previous work, the upper bound is Sota results.

Critical strengths
  1. Clear presentation. The paper is clearly written and well organized, making its structure and main contributions easy to follow.

  2. Matching bounds. The paper provides matching upper and lower bounds, establishing minimax optimality and the tightness of the upper bound under the stated assumptions.

  3. Sound proofs. The proofs appear sound and logically consistent, providing a solid basis for the main theoretical claims.

Critical weaknesses
  1. Limited representativeness. The R-contamination uncertainty model is overly simple and does not adequately represent the range of uncertainties encountered in robust RL games.

  2. Limited algorithmic novelty. FTRL is a standard method in robust RL, and the proposed algorithm offers limited novelty beyond this established framework.

  3. Limited novelty in the analysis. The proofs appear to rely on standard techniques and do not introduce a novel analytical approach.

Questions for authors

Could the authors clarify the key improvements in their proofs compared with prior work? In particular, which technical steps lead to the tighter bound and establish minimax optimality?

4 comments

We sincerely thank the reviewer for the careful reading and recognizing the strengths of our work. Our point-by-point response is as below.

Uncertainty model representativeness. Thank you for your comment about the choice of uncertainty sets. The R-contamination model is an established uncertainty formulation that has been studied in robust single-agent RL [R1-R4], cooperative robust MARL [R5], and online robust MARL [R6]. Other works adopt different uncertainty sets, such as those based on total variation distance or KL divergence, capturing different forms of model uncertainty. To the best of our knowledge, our work establishes the first minimax optimal result for robust MARL under the R-contamination set. Although our model does not cover all these formulations, we believe that establishing its fundamental statistical limits remains valuable. We have added discussion to clarify the scope of result and highlight that our model does not cover other formulations in Section 3.2 (line 401-403) of the revised manuscript.

Algorithmic novelty. Thank you for your comment. Designing a minimax-optimal algorithm for robust MARL is challenging. We agree that FTRL has already been used to address the curse of multiple agents in robust MARL, for example by Shi et al. (2024a). However, their guarantees incur suboptimal dependencies on horizon HH and accuracy ε\varepsilon, leaving open how to overcome the curse of multiple agents while achieving optimal dependencies on the other problem parameters. To achieve this, we use a single-sample robust Bellman update for each state-individual-action pair in each iteration, whereas Shi et al. (2024a) use a batch of samples to estimate the model. In addition, we calibrate both the variance-dependent bonus βi,h\beta_{i,h} and the FTRL learning rates ηk\eta_k to the uncertainty-dependent value span min⁡H,1/R\min\\{H,1/R\\}, rather than HH as in Shi et al. (2024a). Together with a refined analysis, these designs yield our minimax sample complexity guarantee. We explain the analysis in response to your next comment. We have added the corresponding discussion in Section 3.1 (line 350-354) of the revised manuscript.

Novelty in the analysis. Thank you for your question. It is challenging to establish minimax sample complexity for robust MARL. We clarify the key technical differences through comparisons with Shi et al. (2024a,c), the most closely related works. Shi et al. (2024a) use N=Ω(H2min⁡H,1/Rε−2)N=\Omega(H^2\min\\{H,1/R\\}\varepsilon^{-2}) samples per state-individual-action pair in each iteration, whereas we use only one. Our analysis must therefore control the weighted cumulative estimation error without accurate transition estimates at each iteration. We also reduce the number of iterations KK in each stage hh by a factor of H/min⁡H,1/RH/\min\\{H,1/R\\}, which requires refined control of the span and variance of V^i,h\widehat{V}_{i,h}. This is nontrivial because the bounds for V^i,h\widehat{V}_{i,h}, βi,h\beta_{i,h} and qi,h,skq_{i,h,s}^k must be established jointly. Shi et al. (2024c) estimate QQ-functions over the joint action space. Our approach instead uses estimates indexed by individual actions and avoids explicitly solving for equilibria at each stage. This yields a dependence on ∑iAi\sum_i A_i rather than ∏iAi\prod_i A_i. We have highlighted these technical steps and their differences from prior analyses in Section 3.2 (line 425-431) of the revised manuscript.

In summary, our main contribution is to establish the first minimax-optimal sample complexity for robust MARL under R-contamination model. No prior work has established such a guarantee under any uncertainty model.

[R1] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. NeurIPS, 2021

[R2] Yue Wang and Shaofeng Zou. Policy Gradient Method for Robust Reinforcement Learning. ICML 2022.

[R3] Yue Wang, Alvaro Velasquez, George K. Atia, Ashley Prater-Bennette, and Shaofeng Zou. Model-Free Robust Average-Reward Reinforcement Learning. ICML 2023.

[R4] Zhengfei Zhang, Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Distributionally Robust Constrained Reinforcement Learning under Strong Duality. RLJ, RLC, 2024.

[R5] Yudan Wang, Yue Wang, Yi Zhou, Alvaro Velasquez, and Shaofeng Zou. Data-Driven Robust Multi-Agent Reinforcement Learning. IEEE MLSP 2022.

[R6] Shaocong Ma, Ziyi Chen, Shaofeng Zou, and Yi Zhou. Decentralized robust V-learning for solving markov games with model uncertainty. JMLR, 2023

Thank you again for your time and effort in reviewing our paper. As the discussion period will end in one day, we would appreciate it if you could let us know whether you have any further concerns.

Thanks for the response. My concern is the limited impact of the analysis under contamination models. The references added here are mostly early studies of robust RL, and people have known that contamination models are linear and thus less challenging than non-linear models like total variation or divergence. In fact, it has been proven that a robust MDP under a contamination model can be solved by a standard MDP with a reduced discount factor. Therefore, it is unclear how this analysis can be extended or how impactful it is. Thus, I will keep my score.

Thank you for your follow-up. We recognize the importance of extending the analysis to other uncertainty sets and will study this direction in future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.