Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

Motivation

• Existing online DRMG methods face off-dynamics learning and scalability challenges, while established intrinsic-complexity measures do not directly extend to general-sum robust multi-agent systems.Agents collect data under nominal dynamics but seek equilibria under worst-case dynamics; joint action spaces can grow exponentially, and existing measures rely on a single Bellman operator.Source: §1 · p. 2

RoMEX-ϕ

• RoMEX-ϕ combines a dual reformulation of the robust multi-agent Bellman operator with fitted learning to estimate worst-case values from nominal data.Centered empirical robust discrepancy and regularized payoffs provide global regularization that guides coordinated exploration.Source: §1 · p. 2

Robust MADC

• Robust MADC characterizes how empirical robust Bellman errors under nominal data control value prediction under worst-case dynamics across interacting agents and policy-induced distributions.It captures strategic coupling and equilibrium structure while accounting for the mismatch between nominal learning and adversarial evaluation.Source: §1 · p. 2

Regret guarantees

• RoMEX-ϕ has a first sublinear robust regret guarantee for online general-sum DRMGs with general function approximation, with no explicit dependence on state- or joint-action-space sizes.The bound separates intrinsic exploration complexity, governed by robust MADC, from robust Bellman estimation cost incurred using nominal data.Source: §1 · p. 2

Numerical validation

• RoMEX-ϕ is reported to be substantially more resilient to transition shifts than its non-robust counterpart and competitive with an exact tabular robust baseline.The experiments use a scalable general-sum DRMG under total variation uncertainty.Source: §1 · pp. 2–3

Tabular Distributionally Robust Markov Games

• Prior online DRMG methods rely on explicit state–action enumeration and per-state exploration, limiting scalability to large or continuous domains.Existing approaches also include restrictive uncertainty-level conditions and dependence on joint action space size.Source: §2 · p. 3

Single-agent distributionally robust RL with function approximation

• Robust learning with function approximation has largely relied on structured settings or offline coverage, while nominal online methods do not address distributional robustness.Robust Bellman operators are not directly observable from nominal data and may violate standard realizability assumptions.Source: §2 · p. 3

Non-robust MARL with function approximation

• Intrinsic-complexity methods for non-robust MARL do not provide a unified account of exploration under strategic interaction in general-sum games.Zero-sum methods rely on minimax structure, while many general-sum approaches rely on linear classes or other structure.Source: §2 · p. 3

Intrinsic complexity and robust MARL

• MADC measures how in-sample Bellman error translates into out-of-sample value prediction under strategic interaction, but the related framework concerns nominal MARL.The paper contrasts this with robust settings, where nominal data must support worst-case value prediction.Source: §2 · p. 4

Research gap

• The paper identifies a gap in combining robustness, equilibrium learning, and general function approximation in a purely online, model-free setting.Its proposed framework combines dual-based robust Bellman estimation, equilibrium-based policy learning, and robust MADC.Source: §2 · p. 4

DRMG formulation

• The game uses agent-wise rectangular uncertainty sets, specified independently across horizons, states, and joint actions.The formulation considers ϕ-divergence uncertainty sets; support inclusion is addressed for TV, χ2, and KL sets under the stated conditions.Source: §3 · pp. 4–5

Robust value functions

• Each agent seeks to maximize its value against worst-case transition kernels from its own uncertainty set.The robust value functions follow robust Bellman equations.Source: §3 · p. 5

DRMG equilibria

• Robust NE, CCE, and CE require that agents cannot improve robust value through unilateral deviation, with CCE and CE also considered for computational tractability.The section defines the corresponding approximate equilibrium notions.Source: §3 · p. 5

Online learning objective

• Agents learn through direct interaction with the nominal environment, and robust regret measures accumulated equilibrium gap over episodes.The online protocol executes a policy to collect samples and then updates it.Source: §3 · p. 5

Model-Free General Function Approximation

• The method represents robust action-value functions with structured function classes instead of tabular state–action values.The candidate functions approximate robust value functions, and the analysis adopts completeness to ensure closure under the robust Bellman backup.Source: §4 · p. 6

Dual formulation and functional optimization

• Functional dual optimization replaces repeated pointwise optimization over state–action pairs with a single global optimization over a dual function.Minimizing the dual loss recovers the robust Bellman operator in expectation under the policy-induced visitation distribution.Source: §4 · p. 6

Empirical dual minimization and operator approximation

• The empirical dual minimizer is used to approximate the robust Bellman operator, with a bounded dual loss and restricted dual-function range assumed.The function class approximates the dual solution, and the method plugs the resulting minimizer into the approximate Bellman update.Source: §4 · pp. 6–7

Uniform dual-operator approximation

• Under finite function classes and the stated assumptions, empirical dual optimization uniformly approximates the robust Bellman operator over policies and their induced state–joint action distributions.The approximation is controlled globally under an L1 norm, supporting robust confidence sets and a shared error term for the algorithm and analysis.Source: §4 · p. 7

• At each stage, RoMEX-ϕ first minimizes an empirical dual loss on prior data, then fits the next-stage value by minimizing a plug-in robust Bellman residual.Source: §5 · pp. 7–8
• The discrepancy uses a dual-induced robust integrand rather than the nominal transition expectation, making the robust Bellman target tractable on observed data.Source: §5 · p. 8
• A regularized robust payoff favors high estimated robust value while penalizing empirical robust Bellman discrepancy, trading value estimation against Bellman consistency without an explicit optimistic bonus.Source: §5 · p. 8
• The algorithm forms a normal-form game from candidate pure joint policies, uses an NE/CCE/CE oracle, and executes the selected policy in the nominal environment to collect a trajectory.Source: §5 · pp. 8–9

6 Theoretical Guarantee

• Robust MADC measures how nominal-data robust Bellman training errors control value-prediction errors under worst-case dynamics, capturing exploration difficulty from strategic interaction and transition uncertainty.It also reflects alignment between the function class and robust Bellman operator: smaller empirical robust errors translate into smaller prediction errors.Source: §6 · p. 9
• RoMEX-ϕ’s regret bound combines robust-MADC exploration, a horizon-dependent burn-in term, robust Bellman estimation, and dual approximation error.The robust-estimation term reflects the cost of approximating the worst-case Bellman operator from nominal data and depends on primal and dual function-class complexity; the dual approximation error vanishes under realizability.Source: §6 · p. 10
• Online-to-batch conversion yields the first sample-complexity guarantees for ε-optimal RoMEX-ϕ policies, governed by robust MADC without explicit dependence on |S| or |A|.The analysis replaces tabular joint-action dependence with intrinsic function-class complexity, improving scalability over tabular robust MARL.Source: §6 · pp. 9–10

6.1 Novelties of RoMEX-ϕ

• RoMEX-ϕ constructs regularized robust payoffs by estimating a functional dual minimizer from nominal data, plugging it into fitted robust Bellman recursion, and penalizing centered empirical robust discrepancy.The discrepancy measures excess robust Bellman inconsistency relative to the best in-class approximation, enabling a global uncertainty measure under general function approximation.Source: §6.1 · pp. 10–11
• The centered discrepancy supports equilibrium-based learning by regularizing robust payoffs in a surrogate game over pure joint policies, guiding selection toward robust values and statistically reliable fitted recursions.The equilibrium oracle operates on these regularized payoffs, combining robust policy evaluation with equilibrium-based exploration.Source: §6.1 · p. 11
• Centering enables telescoping control of estimation errors across episodes by eliminating plug-in-operator bias, while robust MADC links nominal-data Bellman errors to adversarial-dynamics value prediction.The framework jointly controls approximation, statistical generalization, and strategic deviation errors, yielding an intrinsic-complexity characterization for online exploration in general-sum DRMGs.Source: §6.1 · p. 11

6.2 Comparison with Prior Works

• The robust MABE-to-MADC implication connects robust Bellman-error complexity to exploration complexity, while robust estimation contributes a separate term for nominal-to-worst-case distribution mismatch.In the tabular setting, the framework recovers uncertainty-dependent scaling; under structured function classes, robust MADC can instead be smaller than tabular state–joint-action complexity.Source: §6.2 · p. 13
• Under robust-to-nominal feature coverage, Theorem 4 supplies the linear specialization’s drob,max term, which Theorem 1 uses to derive the linear rows in Table 1.The section presents this as a direct specialization of the general robust bilinear framework.Source: §6.2 · p. 14
• Compared with [85], the TV bound has worse horizon and uncertainty dependence, but the framework applies uniformly to TV, χ2, and KL uncertainty sets.The section calls the result complementary to linear-specific analyses rather than minimax-optimal for linear settings.Source: §6.2 · p. 14
• The framework unifies general-sum DRMG analysis across general function approximation and multiple ϕ-divergence sets, separating intrinsic exploration complexity, MADC, and divergence geometry Ψϕ(σ).This separation distinguishes structural, statistical, and uncertainty-model effects.Source: §6.2 · p. 14
• Specialized tabular or linear methods can achieve sharper rates by exploiting problem structure, while decentralized linear methods reduce joint-exploration burden but require linear realizability and specialized designs.The cited robust linear analysis [85] is tailored to linear structure and TV uncertainty, yielding sharper horizon and TV-radius dependence.Source: §6.2 · p. 14

7.1 Experimental Setup

• The evaluation tests robust training, function-approximation performance against a tabular method, and dual approximation error in a scalable general-sum DRMG.Risky-Coordination uses four agents and a horizon of two; contexts vary state-space size without changing transitions or rewards.Source: §7 · p. 14, §7.1 · p. 14

7.2 Results

• At σ = 0.4, MAMEX falls from 0.392 to 0.063, while RoMEX-ϕ falls from 0.338 to 0.277; their returns cross near σ ≈ 0.1.Figure 1a shows the transition-shift comparison; robust training gives up some nominal return but degrades more slowly under shift.Source: §7.2 · p. 15, Figure 1 · p. 15
• RoMEX-ϕ remains competitive with MORNAVI around the training radius and achieves higher return at larger shifts, despite using learned functions instead of explicit tabular robust planning.Across the shift sweep, MORNAVI decreases from approximately 0.367 to 0.156, while RoMEX-ϕ degrades substantially less.Source: §7.2 · pp. 15–16, Figure 1 · p. 15
• Increasing dual-network width from 8 × 8 to 256 × 256 reduces empirical approximation error from 0.224 ± 0.032 to 0.099 ± 0.002.The experiment is consistent with the assumption that a richer dual class reduces approximation error, but does not establish that assumption generally.Source: Figure 1 · p. 15, §7.2 · p. 16

7.3 Ablation: Sensitivity to the Robustness Radius

• At σ = 0.4, average return rises from 0.037 at σtrain = 0 to 0.214 at 0.1 and 0.254 at 0.2; larger radii add little observed gain.At nominal deployment, positive robustness radii modestly reduce average return from 0.366 to approximately 0.33–0.35; differences among larger radii are not meaningfully ordered given variability.Source: §7.3 · p. 16, Table 2 · p. 16

7.4 Discussion and Limitations

• The experiments use independent per-agent learners, focus on TV uncertainty, and are intended as controlled validation rather than comprehensive benchmarking.MORNAVI uses a Hoeffding-style exploration bonus rather than the tighter Bernstein-type bonus in its theoretical analysis.Source: §7.4 · p. 16

8 Conclusion

• RoMEX-ϕ studies online general-sum DRMG learning with general function approximation, introduces robust MADC, and establishes sublinear robust-regret guarantees without explicit state- or joint-action-space dependence.The conclusion identifies richer function classes and decentralized or partially observed settings as future directions.Source: §8 · p. 17

B Dual Formulation and Functional Optimization

• The functional formulation optimizes over dual functions under the nominal policy-induced state–joint-action visitation distribution, rather than performing pointwise dual optimization.The dual-loss minimization is shown equivalent to the robust support function for the multi-agent setup.Source: B Dual Formulation and Functional… · p. 22
• The functional optimization proof interchanges minimization and expectation after checking decomposability, measurability, and lower semicontinuity conditions.It applies the Rockafellar–Wets integral-interchange result to the dual objective.Source: B Dual Formulation and Functional… · pp. 23–24

C Proof of Lemma 1

• The proof identifies the robust Bellman term with the dual infimum under an averaged visitation distribution, then uses its pointwise nonnegativity.The dual reformulation and Lemma 2 supply the robust support-function identity used in this comparison.Source: C Proof of Lemma 1 · pp. 24–25
• The proof compares the empirical dual minimizer with the population objective, bounding approximation error and empirical excess risk to control the discrepancy.The approximation step invokes Assumption 2, while the excess-risk step uses uniform concentration over the function and policy classes.Source: C Proof of Lemma 1 · pp. 25–26
• The empirical-to-population bound uses a bounded martingale-difference sequence and Freedman’s inequality, with a union bound over hypothesis and policy classes.The proof notes that adaptivity of the behavior-policy sequence is absorbed by the martingale structure rather than included in the union bound.Source: C Proof of Lemma 1 · p. 26

D Proof of Theorem 1

• The CCE and CE arguments reuse the Nash-case bounds, replacing the deviation with a coarse deviation or strategy modification.Both proof cases retain the same played-policy term and its robust MADC control.Source: D Proof of Theorem 1 · pp. 27, 30
• For the Nash case, the proof decomposes regret into deviation-side and played-policy terms, bounding them with benchmark comparisons and robust MADC.The played-policy term is controlled using the robust MADC inequality together with Lemma 5.Source: D Proof of Theorem 1 · pp. 27–28
• The proof establishes robust regret bounds for NE, CCE, and CE by applying each surrogate equilibrium’s corresponding deviation inequality.The theorem covers the three equilibrium notions; sum-over-agent regret incurs an additional factor m in the CCE and CE cases described.Source: D Proof of Theorem 1 · pp. 27, 29, 30

D.1 Regret bound under χ2 and KL

• The derivation uses one-dimensional variational forms for TV, χ2, and KL, focusing here on χ2 and KL.The TV case is referred to the appendix.Source: §D.1 · p. 31
• The corollary gives a sample-complexity guarantee for obtaining an ε-robust equilibrium, using σmax := maxi∈M σi.The supplied passage states the guarantee but does not include the full complexity expression.Source: §D.1 · p. 31
• For χ2 and KL uncertainty, the divergence-specific bounds are Bχ2(σi) = O(H(1 + √σi)) and BKL(σi) = O(H max{1, σi}).These bounds are substituted into the general sample-complexity result.Source: §D.1 · p. 32
• RoMEX-ϕ yields an ε-robust equilibrium policy for NE, CCE, or CE under the stated choice of T.The CCE and CE guarantees follow from the same online-to-batch argument as the NE case.Source: §D.1 · p. 32

E Theoretical Guarantee of TV-divergence Uncertainty Set

• The TV analysis uses the failure-states assumption, requiring zero reward on each agent’s specified failure states.The passage also specifies a transition condition, but its statement is incomplete here.Source: E Theoretical Guarantee of… · p. 32
• The robust-to-nominal concentrability condition bounds the relationship between worst-case occupancy and historical nominal data distributions.It is defined for agents, stages, episodes, and policies in the stated policy family.Source: E Theoretical Guarantee of… · p. 33
• Under Definition 7, RoMEX-ϕ has a unified robust equilibrium-regret bound for TV-divergence uncertainty.The theorem states the bound with probability at least 1 − δ.Source: E Theoretical Guarantee of… · p. 33
• With the stated assumptions, RoMEX-TV has a sample-complexity guarantee for an ε-robust equilibrium policy.The guarantee assumes TV-divergence, robust-to-nominal concentrability, and the failure-states assumption.Source: E Theoretical Guarantee of… · p. 33
• The robust CCE and CE regret bounds follow by applying the corresponding deviation inequalities, alongside the robust NE case.The same result covers Eq ∈ {NE, CCE, CE}.Source: E Theoretical Guarantee of… · p. 34

F Multi-Agent Robust Bellman Eluder Dimension

• Theorem 3 establishes that low robust MABE implies low robust MADC under the stated model-free setup.The result is stated for a fixed agent and an arbitrary integer K.Source: F Multi-Agent Robust Bellman Eluder… · p. 35
• Robust MADC links empirical robust Bellman errors computed from nominal data to value prediction under worst-case transition dynamics.Its analysis distinguishes nominal historical visitation distributions from worst-case occupancy measures.Source: F Multi-Agent Robust Bellman Eluder… · p. 35
• RoMEX-ϕ has sublinear robust equilibrium regret whenever the robust MABE dimension is finite.The regret bound is obtained by combining Theorem 1 with Theorem 3.Source: F Multi-Agent Robust Bellman Eluder… · p. 39
• The regret decomposition includes an exploration term governed by robust MADC and a robust-estimation term arising from approximating the worst-case Bellman operator with nominal data.It also includes a lower-order horizon-dependent contribution and dual-function approximation error.Source: F Multi-Agent Robust Bellman Eluder… · p. 39
• The robust-setting complexity additionally reflects the difficulty of estimating the robust Bellman operator from nominal data and a divergence-dependent envelope.Structural conditions yielding low decoupling complexity translate into sample-efficient online learning.Source: F Multi-Agent Robust Bellman Eluder… · p. 39

Robust Multi-Agent Bilinear Classes

• The robust class extends [78] by requiring a bilinear factorization of robust Bellman residual means in a Hilbert space over admissible stage-wise distributions, including nominal visitation and worst-case occupancies.This preserves the factorization structure for learning while accommodating worst-case transition dynamics.Source: G Robust Multi-Agent Bilinear Classes · pp. 39–40
• Under robust-to-nominal feature coverage, robust multi-agent bilinear classes have finite robust MADC, which supports sample-efficient learning.The theorem’s bound also assumes a uniform bound on robust value functions.Source: G Robust Multi-Agent Bilinear Classes · pp. 40, 41, 43
• Robust linear Bellman-complete DRMGs form a tractable subclass because each agent’s linear Q-function class remains closed under robust Bellman updates.Robust linear examples require explicit robust Bellman completeness or robust support linearity because the robust support operator is generally nonlinear in the value function.Source: G Robust Multi-Agent Bilinear Classes · pp. 40, 45
• In robust linear Bellman-complete DRMGs, RoMEX-ϕ achieves robust equilibrium regret scaling polynomially in the horizon and linearly in feature dimension, up to logarithmic factors, with mismatch reflected through C0.The result follows from finite robust bilinear information gain and robust MADC under robust-to-nominal feature coverage.Source: G Robust Multi-Agent Bilinear Classes · p. 46

G Robust Multi-Agent Bilinear Classes

• RoMEX-ϕ achieves sublinear robust equilibrium regret in the zero-sum robust linear subclass, with distribution mismatch entering through C0.The guarantee holds up to logarithmic factors and gives an explicit structured class with finite robust MADC.Source: G Robust Multi-Agent Bilinear Classes · p. 47
• For the total-variation case, the revised regret bound applies Definition 7 and uses Ccov ≥ 1 instead of C0.This adjustment handles the support-shift issue.Source: G Robust Multi-Agent Bilinear Classes · p. 48
• Unlike nominal transition linearity, robust Bellman closure does not follow automatically; the zero-sum specialization verifies it through an additional robust support-linearity condition.The robust support operator is nonlinear in the continuation value, motivating support-linearity for constructive closure verification.Source: G Robust Multi-Agent Bilinear Classes · pp. 46, 48
• The robust information gain is Õ(Hdlin), and robust-to-nominal feature coverage yields robust MADC of order Õ(γ^2Hdlin), enabling sublinear regret.Robust information gain alone does not control value prediction because nominal training distributions can mismatch worst-case occupancies.Source: G Robust Multi-Agent Bilinear Classes · pp. 47–48

H Auxiliary Lemmas

• Lemma 3 establishes a surrogate unilateral-deviation inequality for Nash, coarse correlated, and correlated equilibrium outputs.The proof applies each equilibrium notion’s deviation property to the surrogate normal-form game.Source: H Auxiliary Lemmas · pp. 48–49
• Lemma 4 relates robust payoff performance under worst-case occupancy to the fitted plug-in surrogate value through the cumulative centered empirical robust discrepancy.The proof uses a robust Bellman telescoping identity and adds and subtracts the dual plug-in operator.Source: H Auxiliary Lemmas · pp. 49–50
• Lemma 5 states a robust empirical discrepancy concentration result under Assumptions 1–3; for K ≥ Λ_i, its stated guarantee holds with probability at least 1−δ.Source: H Auxiliary Lemmas · p. 50
• Lemma 6 gives a high-probability concentration guarantee for a Bellman-consistent robust benchmark when K ≥ Λ_i, with an additional plug-in operator-approximation term controlled by Lemma 1.The proof uses uniform excess-risk concentration and Freedman’s inequality; unlike the non-robust proof, the benchmark is a fixed point of the true robust Bellman operator while the empirical discrepancy uses a plug-in operator.Source: H Auxiliary Lemmas · pp. 54–55
• A uniform concentration event permits substituting empirical dual minimizers, while a plug-in Bellman comparator cancels conditional next-state variance before operator-approximation error is bounded.The comparator is first fixed to avoid measurability issues, then specialized to the empirical dual minimizer because concentration holds uniformly over dual functions.Source: H Auxiliary Lemmas · pp. 56–58
• Under Assumptions 1–3, robust-to-nominal concentrability with constant Ccov, and the uniform dual-switch stability event, Lemma 7 establishes a benchmark-to-surrogate comparison with probability at least 1−δ, uniformly over all (i,k,π).Source: H Auxiliary Lemmas · p. 58

I Covering and Bracketing Numbers.

• For infinite function classes, a δ-covering number is the smallest size of a subset whose members lie within distance δ of every class member.The supremum-norm covering number is abbreviated NF(δ).Source: I Covering and Bracketing Numbers · p. 60
• A δ-bracketing number is the minimum number of function-pair brackets that uniformly bound their gap by δ and sandwich each class member's policy-trajectory value.Each bracket must satisfy the gap condition for every policy and bound the value for all admissible trajectories.Source: I Covering and Bracketing Numbers · p. 61

J Technical Lemmas

• An optimizer of the integral problem is characterized by solving the pointwise minimization problem almost everywhere, provided the common infimum is greater than −∞.Source: J Technical Lemmas · p. 61
• The ERM lemma gives an excess-risk guarantee for an empirical minimizer under bounded loss, using the empirical Rademacher complexity of the loss-composed function class.It assumes an i.i.d. sample and defines the comparator as a minimizer of expected loss.Source: J Technical Lemmas · p. 61
• The appendix recalls Freedman’s inequality for bounded martingale differences and an elliptical potential inequality for cumulative self-normalized squared norms.The cited proof of the latter invokes self-normalized processes and log-determinant monotonicity.Source: J Technical Lemmas · p. 62