acceptodds
Withdrawn from ICLR 2027

Online Robust Multi-Agent Learning with General Function Approximation

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Distributionally robust Markov games (DRMGs) provide a principled framework for handling model misspecification in multi-agent reinforcement learning, but existing methods often rely on restrictive assumptions or scale poorly to large-scale problems. In this work, we study online multi-agent reinforcement learning in general-sum DRMGs with general function approximation and -divergence uncertainty sets. We propose RoMEX-, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. By reformulating the robust multi-agent Bellman operator via a functional dual representation, our approach enables tractable worst-case value estimation from nominal data through a unified objective based on a centered empirical robust discrepancy. To quantify the learning complexity, we introduce the *robust Multi-Agent Decoupling Coefficient* (robust MADC) to characterize intrinsic exploration complexity under adversarial dynamics. With this notion, we further establish sublinear regret guarantees of our RoMEX-, which rely explicitly on robust MADC instead of the large state and action spaces, and hence significantly improve the scalability and efficiency of robust multi-agent reinforcement learning in large-scaled multi-agent systems.

Primary area:
reinforcement learning
Keywords:
multi-agent learning, robust RL, functional approximation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Cz6oOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online learning within the framework of distributionally robust general-sum Markov games, where agents act robustly towards an uncertainty set of environment transitions measured by ϕ\phi-divergence. It proposes a learning framework, RoMEX-ϕ\phi, which uses general function classes to approximate the value functions and estimate the functional dual representation. To obtain the sample complexity of the proposed algorithm, the robust MADC coefficient is introduced to measure the intrinsic exploration complexity. Then, a sublinear regret upper bound is presented with polynomial dependence on the problem's related parameters. The proposed algorithm is further supported by experimental results in appendix.

Critical strengths
  1. The online learning problem of the robust multi-agent general-sum Markov game problem with general function approximation is challenging, especially with model-free methods. Therefore, the focus of this paper is worthwhile and meaningful.
Critical weaknesses
  1. In Assumption 2, it requires the function class Gi\mathcal{G}_i to have a similar optimization value of the LossDual objective to the function class L1\mathcal{L}_1. Given Gi\mathcal{G}_i is finite by Lemma 3, it is unclear how can ϵapprox\epsilon^{approx} be controlled. Since a finite class and the L1\mathcal{L}_1 function class is substantially different.

  2. A possible technical flaw was identified, and the proof needs to be checked more carefully. For example, in Appendix L, Equation~(187), the authors observe that inf⁡f′L(f′)≤L(fˉ),\inf_{f'} L(f') \le L(\bar{f}), but then conclude

\le L(f^\star) - L(\bar{f}).$$
Questions for authors
  1. What is the value of $ \epsilon^ {approx} $ in Assumption 2 in general? Can you provide some examples that $ \epsilon^ {approx} $ can be less than an arbitrary non-negative value? If it is a non-negligible constant, how it affect your final upper bound and policy optimality?

  2. The robust MADC coefficient is claimed to guide exploration and exploitation, while in a general online learning RL framework, the optimistic bonus term are used. How to estimate this MADC coefficient?

  3. What is the main technical novelty of this paper, compared to prior works? For example, (Panaganti et al., 2022) and (Xiong et al., 2024)

Reference

Nuoya Xiong, Zhihan Liu, Zhaoran Wang, and Zhuoran Yang. Sample-Efficient Multi-Agent RL: An Optimization Perspective. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.

Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust Reinforcement Learning using Offline Data. Advances in neural information processing systems, 35:32211–32224, 2022.

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

The paper studies online learning in general-sum distributionally robust Markov games with general function approximation. It proposes RoMEX-ϕ\phi, combining functional dual estimation of robust Bellman operators, fitted value estimation, and equilibrium computation over a normal-form game of policies. The theoretical contribution is a robust multi-agent decoupling coefficient and a regret guarantee expressed through this coefficient and dual-estimation complexity.

Critical strengths
  • Extending function-approximation guarantees to general-sum robust games and multiple equilibrium notions would be a useful contribution.
  • Separating exploration complexity from robust Bellman-estimation error provides a potentially useful perspective.
Critical weaknesses
  • This paper assumes a distributionally robust Markov game only has state transition kernels' uncertainty. However, there could be other uncertainty sources, like reward uncertainty, state uncertainty, etc. Please add a related work section to investigate relevant work.
  • This paper tries to design a robust MARL algorithm for DRMGs without restrictive assumptions, but assumptions 1~3 seems pretty restrictive. Are there any practical examples that satisfy these assumptions?
  • There is no experiment to verify the effectiveness of the algorithm. There is no baseline.
  • typo: line 196, "n standard RL".
Questions for authors
  • What's the motivation to consider worst-case transition kernels? Is there a practical reason for it? How it is related to Dec-POMDP?
Reviewer_2JKMOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies online distributionally robust learning in finite-horizon general-sum Markov games with general value-function and dual-function approximation. RoMEX-ϕ\phi estimates dual robust Bellman targets from nominal trajectories, fits value functions, assigns regularized payoffs to pure joint policies, and invokes a normal-form equilibrium oracle. The paper introduces a robust multi-agent decoupling coefficient and claims sublinear regret for robust Nash, coarse correlated, and correlated equilibrium learning, together with specializations to structured function classes. Appendix F provides controlled experiments under total-variation uncertainty.

Critical strengths
  1. The problem setting is meaningful. Learning robust equilibria from nominal online interaction with general function approximation requires accounting for distribution shift and strategic deviations. A correct result in this setting would be useful for understanding the statistical requirements of robust multi-agent learning.

  2. Appendix F provides a transparent controlled study of the robustness versus nominal-performance trade-off and the role of dual-function capacity. The appendix explicitly acknowledges that the implementation replaces the full equilibrium oracle. This makes the scope of the experimental evidence easier to assess (pp. 25–27).

Critical weaknesses
  1. Theorem 1 fails with fixed approximation error, and the proof does not establish the claimed cumulative rate. The following construction uses the dual-loss and plug-in conventions in Eqs. (4), (7), and (9). The sign inconsistencies elsewhere are identified in Question 4. Consider H=2H=2 with one active agent; a one-action, zero-reward agent can be added if needed. From either state, first-stage actions a,ba,b deterministically reach states x,yx,y, respectively, with terminal rewards r2(x)=0.8r_2(x)=0.8 and r2(y)=0.775r_2(y)=0.775. Let r1=0r_1=0, and make terminal rewards action-independent. Take the KL generator ϕ(t)=tlog⁡t\phi(t)=t\log t and radius c=σ=0.1c=\sigma=0.1. Support inclusion preserves these deterministic transition rows. Let q=(0.8,0.775)q=(0.8,0.775), F3={0}\mathcal F_3=\{0\}, F2={r2,r2−c}\mathcal F_2=\{r_2,r_2-c\}, and F1={q,q−c,qapp}\mathcal F_1=\{q,q-c,q_{\mathrm{app}}\}, where qapp=(0.6,0.625)q_{\mathrm{app}}=(0.6,0.625); first-stage functions are state-independent. Let G2={(λ,ν)=(1,1)}\mathcal G_2=\{(\lambda,\nu)=(1,1)\}. The two functions in G1\mathcal G_1 share λ=(1,1/2)\lambda=(1,1/2), with ν=q+λ\nu=q+\lambda and ν=q−c+λ\nu=q-c+\lambda, respectively. Assumption 1 holds because the exact Bellman backups are r2,q,q−cr_2,q,q-c. For deterministic continuation VV, the dual loss at ν=V+λ\nu=V+\lambda equals λc−V\lambda c-V, so Assumption 2 holds uniformly with εdualapprox=c\varepsilon_{\mathrm{dual}}^{\mathrm{approx}}=c. The finite set of these five parameter pairs provides a compact Θϕ\Theta_\phi with envelope B=2B=2, satisfying Assumption 3. All F1\mathcal F_1 hypotheses underestimate qq, so Definition 4 admits dMADC=1d_{\mathrm{MADC}}=1. After any first episode, the unique terminal fit is r2−cr_2-c. The unique first-stage dual choice is the second function, giving target q−c−λc=qappq-c-\lambda c=q_{\mathrm{app}}, which is the unique least-squares fit on either observed action. Both stages have zero residual, hence Eq. (11)’s penalty is zero. The oracle therefore always selects bb from episode 2 onward, although aa is better by 1/401/40. Thus Reg⁡(K)≥(K−1)/40\operatorname{Reg}(K)\ge (K-1)/40 deterministically, contradicting Theorem 1’s O(Klog⁡K+0.1)O(\sqrt{K\log K}+0.1) bound with all classes and constants fixed (Algorithm 1, p. 6; Eqs. (10)–(11), p. 7; Theorem 1, p. 8). A fixed approximation error cannot generally enter this cumulative-regret guarantee only as a term independent of KK. The proof treats this fixed error as a freely adjustable tolerance. Lemma 1 supplies the approximation term εdualapprox\varepsilon_{\mathrm{dual}}^{\mathrm{approx}} for the given class G\mathcal G, whereas the proofs using Eqs. (154) and (191) subsequently choose εˉ≤εdualapprox/(HKB)\bar\varepsilon\le\varepsilon_{\mathrm{dual}}^{\mathrm{approx}}/(HKB) (pp. 57 and 63). Assumption 2 does not imply this stronger accuracy condition. For a fixed class with positive approximation error, it cannot hold for arbitrarily large KK. The analysis must retain the cumulative approximation contribution or supply and analyze stronger assumptions on GK\mathcal G_K. There are also additional prerequisites in the regret proof. Lemma 7 requires Definition 7’s historical coverage condition and a uniform dual-switch stability event (p. 64), neither of which is included in Theorem 1. Eq. (203) asserts the required stability inequality without a probability guarantee derived from Assumptions 1–3. The factor CcovC_{\mathrm{cov}} in Eqs. (205)–(209) disappears from Eq. (33). Transition-row support inclusion does not ensure that the historical data distribution covers every candidate policy. For example, if every previous behavior policy assigns zero probability to action bb at the initial state, while a candidate policy selects bb, the required absolute continuity fails. Even granting Lemmas 5–7 and setting approximation error to zero, Lemmas 5 and 6 provide a per-episode statistical remainder of order HB2KιHB^2\sqrt{K\iota}, where ι\iota denotes the logarithmic complexity factor. Summing over the outer episode index gives HB2KKιHB^2K\sqrt{K\iota}. Eqs. (34) and (39) instead use HB2KιHB^2K\sqrt{\iota}; Eq. (33) makes the analogous unsupported improvement in its β\beta-weighted term. No sharper cumulative estimate is established. With the stated μ=K\mu=\sqrt K and β=2/K\beta=2/\sqrt K, direct use of these lemmas leaves a statistical term O(HB2Kι)O(HB^2K\sqrt{\iota}). Thus the displayed argument does not establish the claimed square-root regret rate.

  2. The centered discrepancy permits changing the continuation, invalidating Lemma 6. Equation (11) minimizes over the complete sequence f′f^\prime, allowing the comparator to change the continuation fh+1′f^\prime_{h+1} and its sampling variance. This invalidates Lemma 6 (p. 59), even with exact dual approximation. The zero-radius case used below is not excluded by Definition 1 or the assumptions stated for Lemma 6. Consider H=2H=2, one agent, one action, r1=0r_1=0, and states s0,g,b,zs_0,g,b,z, with initial state s0s_0 and r2=1{g}r_2=\mathbf 1_{\{g\}}. At stage 1, every state except the absorbing state zz transitions uniformly to g,bg,b; all stage-2 transitions lead to zz. Let q=1/2q=1/2 outside zz and q(z)=0q(z)=0, and set F1={q,0}\mathcal F_1=\{q,0\}, F2={r2,0}\mathcal F_2=\{r_2,0\}, and F3={0}\mathcal F_3=\{0\}. Take the TV generator ϕ(t)=∣t−1∣\phi(t)=|t-1|, radius σ=0\sigma=0, and G1=G2={(λ,ν)=(1,0)}\mathcal G_1=\mathcal G_2=\{(\lambda,\nu)=(1,0)\}. Since ϕ∗(−V)=−V\phi^*(-V)=-V for every relevant V∈[0,1]V\in[0,1], the dual loss is exactly −V-V. Assumptions 1–3 hold, with εdualapprox=0\varepsilon_{\mathrm{dual}}^{\mathrm{approx}}=0 and B=1B=1. For the Bellman-consistent benchmark f⋆=(q,r2)f^\star=(q,r_2), every first-stage sample residual is ±1/2\pm1/2. The infimum in Eq. (11), however, can choose (f1′,f2′)=(0,0)(f^\prime_1,f^\prime_2)=(0,0), yielding zero first-stage loss. The benchmark’s terminal-stage residual is zero. Consequently, after n=k−1n=k-1 samples, K^k−1(f⋆)=n/4\widehat{\mathcal K}^{k-1}(f^\star)=n/4 on every sample path. At k=Kk=K, this contradicts Lemma 6’s O(Klog⁡K)O(\sqrt{K\log K}) bound for fixed classes. The proof exposes the same problem in Eq. (187), p. 63: inf⁡L≤L(fˉ)\inf L\le L(\bar f) implies L(f⋆)−inf⁡L≥L(f⋆)−L(fˉ)L(f^\star)-\inf L\ge L(f^\star)-L(\bar f), opposite to the displayed inequality. The constructed comparator only fixes the original continuation and need not minimize over all continuations. Correcting the arrow therefore does not provide the required upper bound. A revised discrepancy definition and a corresponding analysis are necessary. The comparator constructions in the proofs of Lemmas 5 and 6 also require an unstated completeness property. Eqs. (168)–(169) (Lemma 5, p. 58) and the comparator in Lemma 6 (p. 62) require closure under the fitted plug-in operator, whereas Assumption 1 only guarantees closure under the exact robust Bellman operator. These two closure conditions are different, so membership of the constructed comparators in the function class has not been justified.

Algorithmic consequence of the local repair. The proposed local repair also raises an algorithmic issue beyond the failure of Lemma 6. If Eq. (11) is repaired by optimizing only the current-stage function while holding the continuation and dual fixed, the stagewise least-squares fit in Line 8 of Algorithm 1 is itself a minimizer of the current-stage empirical loss with that continuation and dual. Each centered term is therefore a minimum minus itself. The repaired discrepancy, denoted K~\widetilde{\mathcal K}, satisfies K~(fk,π;g^k,π;π)=0\widetilde{\mathcal K}(f^{k,\pi};\widehat g^{k,\pi};\pi)=0 for every candidate policy under this repair. The backward fitting order preserves the continuation used in each fit. Consequently, β\beta disappears from the fitted payoff, and this local correction alone does not supply the claimed regularized exploration mechanism.

Questions for authors
  1. Which stated assumption or algorithmic operation excludes the fixed-approximation-error example above? If the update rule or the dependence on approximation error must change, please state the corrected algorithm and cumulative-regret guarantee. In particular, what additional approximation condition justifies εˉ≤εdualapprox/(HKB)\bar\varepsilon\le\varepsilon_{\mathrm{dual}}^{\mathrm{approx}}/(HKB)? If G\mathcal G must improve with KK, please account for class growth, approximation accuracy, and the loss envelope in the corrected bound.

  2. Please provide a corrected discrepancy definition and valid concentration proofs addressing the counterexample and Eq. (187). If only fh′f^\prime_h varies, how will the update avoid the zero regularizer at the fitted sequence? Which condition guarantees completeness for the plug-in comparators in the proofs of Lemma 5 (Eqs. (168)–(169), p. 58) and Lemma 6 (p. 62)?

  3. Please establish the historical coverage and dual-switch stability required by Lemma 7 from Theorem 1’s assumptions, or state the additional assumptions and resulting dependence on CcovC_{\mathrm{cov}}. Please also supply the cumulative argument behind Eqs. (33), (34), and (39), explicitly retaining the outer summation over episodes and any approximation-error accumulation.

  4. Could the authors carry out a consistency and concision revision, with explicit references to the final definitions and the results supporting the algorithmic claims? The following issues concern presentation and mathematical consistency. First, p. 23 says that the rates separate “three effects” but names only intrinsic exploration complexity and divergence geometry. Please supply and explain the missing component or correct the enumeration. Second, clarify the references to “revised” empirical payoffs or discrepancies (e.g., pp. 7, 31–32, 57, 64) by citing the exact final definitions, and identify the cumulative bounds invoked on pp. 31–32. Please clarify or replace “used in the draft” (p. 17) and “This merged example” (p. 53). Lemma 3 (p. 53) also cites Eq. (26) for the regularized payoff, although Eq. (26) is a martingale identity; the payoff is defined in Eq. (10). Please correct this cross-reference. Third, Appendix E (p. 24) repeatedly frames closely related descriptions of dual fitting, the centered discrepancy, and payoff construction as novelty claims. The “does not merely subtract a raw residual” contrast restates the immediately preceding description. This repeated justification of novelty lengthens the discussion without clarifying which property each component establishes. Please consolidate the overlapping explanations into a precise account of the additional mechanism and its established properties, with direct references to the relevant equations and lemmas. Finally, please reconcile the signs in Eq. (3) (p. 4), Lemma 2 (p. 16), and Eq. (14) (p. 17): under the dual-loss convention used in Eqs. (4), (7), and (9), the infimum of the dual loss equals the negative of the robust expectation, consistently with Eq. (2). The explicit limitations about specialized rates and the experimental implementation are useful and should be retained in a concise form.

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

Related papers

Discussion (0)

Sign in to comment.