Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation
Authors: Jake Gonzales, Max Horwitz, Eric Mazumdar, Lillian J. Ratliff
Organizations: Department of Electrical & Computer Engineering, University of Washington · Computing & Mathematical Sciences, California Institute of Technology
Provably efficient and robust equilibrium computation in general-sum Markov games remains a core challenge in multi-agent reinforcement learning. Nash equilibrium is computationally intractable in general and brittle due to equilibrium multiplicity and sensitivity to approximation error. We study Risk-Sensitive Quantal Response Equilibrium (RQRE), which yields a unique, smooth solution under bounded rationality and risk sensitivity. We propose RQRE-OVI, an optimistic value iteration algorithm for computing RQRE with linear function approximation in large or continuous state spaces. Through finite-sample regret analysis, we establish convergence and explicitly characterize how sample complexity scales with rationality and risk-sensitivity parameters. The regret bounds reveal a quantitative tradeoff: increasing rationality tightens regret, while risk sensitivity induces regularization that enhances stability and robustness. This exposes a Pareto frontier between expected performance and robustness, with Nash recovered in the limit of perfect rationality and risk neutrality. We further show that the RQRE policy map is Lipschitz continuous in estimated payoffs, unlike Nash, and RQRE admits a distributionally robust optimization interpretation. Empirically, we demonstrate that RQRE-OVI achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches. These results suggest RQRE-OVI offers a principled, scalable, and tunable path for equilibrium learning with improved robustness and generalization.
Figures & tables
Figure 1: Self-play team return during training. Moving average of team return over episodes for Stag-Hunt (left) and Overcooked (right). In Stag-Hunt, higher τ drives agents toward the payoff dominant ( stag , stag ) outcome, while lower τ yields the more robust risk-dominant ( hare , hare ) outcome. In Overcooked, all RQRE variants and QRE converge to comparable team returns, with Nash variants reaching similar or slightly lower levels.
Figure 2: Cross-play retention (R(δ)/R(0)) as a function of perturbed partner noise ( δ ): Stag-Hunt (left) and Overcooked (right). At each evaluation step, the partner’s action is a fixed deterministic action (e.g., always move in one direction) with probability δ and otherwise follows its trained policy. This produces high-signal deviations to emphasize the robustness phenomena. Curves are normalized by the δ=0 baseline, so higher values indicate strong robustness and lower values indicate performance degradation. Results are averaged over 200 evaluation rollouts per noise level.
Figure 3: Cross-play with unseen partners in Overcooked. Each point represents the reward of two agents trained under a different algorithm and paired at test time without ever seen each other before. The left panel shows RQRE-OVI agent’s reward (vertical axis) versus NQ-OVI agent’s reward (horizontal axis) for each pairing; the right panel reverses the roles. Points above the diagonal indicate that the agent on the vertical axis (in this case RQRE) achieves higher return than its partner. Labels denote the τ value of the corresponding RQRE-OVI agent, and the red diamond marks the QRE-OVI baseline score against NQ-OVI . Across all pairings, RQRE-OVI agents achieve equal or higher ego reward than their cross-play partner, with moderate τ values (e.g., τ=0.01 ) yielding the strongest advantage.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Dynamic Stag Hunt (left) and Overcooked (right) environments used in experiments.
Figure 5: Stag Hunt outcome distributions during training. Each panel shows the fraction of stag–stag, hare–hare, and mixed interaction outcomes (rolling average) for a given algorithm and risk-aversion level. NQOVI, QRE, and low risk averse RQRE agents converge to payoff dominant stag–stag outcomes, while highly risk averse agents to risk dominant hare–hare, confirming the expected equilibrium selection.
Figure 6: Self play performance for each algorithm in Overcooked over 200 evaluation rollouts.
Figure 7: Cross-play with a perturbed partner. Ego agent reward as a function of the partner noise for Stag Hunt (left) and Overcooked (right). At each evaluation step, the perturbed partner’s action is replaced with a fixed deterministic action (e.g., always move in a single direction) with probability δ , and the trained policy is executed otherwise. This deterministic perturbation ensures that deviations are high-signal rather than averaging out under uniform noise. The results are averaged over 200 evaluation rollouts at each noise level.
Category
Hyperparameter
Value
Setup
Episodes ( K )
5000
Feature dimension ( d )
200
Ridge parameter ( λ )
1.0
Exploration bonus ( β )
0.1
Buffer size
1000
Update frequency
10
Appendix
Table 1: Hyperparameters for Stag Hunt experiments
Category
Hyperparameter
Value
Setup
Episodes ( K )
5000
Feature dimension ( d )
685
Ridge parameter ( λ )
5.0
Exploration bonus ( β )
0.1
Buffer size
500
Update frequency
10
Appendix
Table 2: Hyperparameters for Overcooked experiments
Cooperative equilibria are fragile. When agents learn alongside each other rather than in a fixed environment, the process of learning destabilizes the cooperation they are trying to sustain: every gradient step an agent takes shifts the distribution of actions its partner will play, turning a cooperative partner into a source of stochastic noise precisely where the cooperation decision is most sensitive. We study how this co-learning noise propagates through the structure of coordination games, and find that the cooperative equilibrium, even when strongly Pareto-dominant, is exponentially unstable under standard risk-neutral learning, collapsing irreversibly once partner noise crosses the game's critical cooperation threshold. The natural response to apply distributional robustness to hedge against partner uncertainty makes things strictly worse: risk-averse return objectives penalize the high-variance cooperative action relative to defection, widening the instability region rather than shrinking it, a paradox that reveals a fundamental mismatch between the domains where robustness is applied and instability originates. We resolve this by showing that robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution. This distinction yields an algorithm whose gradient updates are modulated by an online measure of partner unpredictability, provably expanding the cooperation basin in symmetric coordination games. To unify stability, sample complexity, and welfare consequences of this approach, we introduce the Price of Paranoia as the structural dual of the Price of Anarchy. Together with a novel Cooperation Window, it precisely characterizes how much welfare learning algorithms can recover under partner noise, pinning down the optimal degree of robustness as a closed-form balance between equilibrium stability and sample efficiency.
Deep Kumar Ganguly, Chandradithya S Jonnalagadda, Pratham Chintamani +1
Technical University of Munich (TU Munich) · Brown University · Indian Institute of Technology Tirupati (IIT Tirupati)
Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online 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. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-φ enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-φ is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.
Debamita Ghosh, George K. Atia, Yue Wang
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, FL 32816, USA · Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA
We propose and study distributionally robust Markov games (DR-MGs) with the average-reward criterion as a crucial framework for multi-agent decision-making under model mismatches and over extended horizons. Under a standard irreducible assumption, we first derive a correspondence between the optimal policies and the solutions of the robust Bellman equation, based on which we further show the existence of a stationary Nash Equilibrium (NE) of the game. We further study DR-MGs under a more general weakly communicating setting. We construct a set-valued map based on the constant-gain optimal robust Bellman operator and show that its value is a subset of the best-response policies. We further prove that this map admits a fixed point, which implies the existence of NE. We then design two algorithms, Robust Nash-Iteration and robust TD Descent, with provably convergent guarantees. Finally, we show that the NE under average-reward can be approximated by the ones for the discounted DR-MGs as the discount factor approaches one. Our studies provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments.
Zachary Roch, Yue Wang
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.