cs.LGMar 10, 2026

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 τ\tau drives agents toward the payoff dominant ( stag , stag ) outcome, while lower τ\tau 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))(R(\delta)/R(0)) as a function of perturbed partner noise ( δ\delta ): 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 δ\delta and otherwise follows its trained policy. This produces high-signal deviations to emphasize the robustness phenomena. Curves are normalized by the δ=0\delta=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 τ\tau 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 τ\tau values (e.g., τ=0.01\tau=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 δ\delta , 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.
CategoryHyperparameterValue
SetupEpisodes ( KK )5000
 Feature dimension ( dd )200
 Ridge parameter ( λ\lambda )1.0
 Exploration bonus ( β\beta )0.1
 Buffer size1000
 Update frequency10
Appendix
Table 1: Hyperparameters for Stag Hunt experiments
CategoryHyperparameterValue
SetupEpisodes ( KK )5000
 Feature dimension ( dd )685
 Ridge parameter ( λ\lambda )5.0
 Exploration bonus ( β\beta )0.1
 Buffer size500
 Update frequency10
Appendix
Table 2: Hyperparameters for Overcooked experiments
More in this topic

Multi-Agent Reinforcement Learning

Multi-agent reinforcement learning studies how interacting agents learn coordinated or competitive policies through shared experience and rewards.

See all 362 papers

Explore similar work

CardsList

  1. The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning

    Apr 17, 2026Deep Kumar Ganguly, Chandradithya S Jonnalagadda, Pratham Chintamani +1Multi-Agent Reinforcement LearningMulti-Agent Coordination

    Technical University of Munich (TU Munich) · Brown University · Indian Institute of Technology Tirupati (IIT Tirupati)

  2. Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

    Sep 25, 2026Debamita Ghosh, George K. Atia, Yue WangFunction Approximation in RLReinforcement Learning

    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

  3. Distributionally Robust Markov Games with Average Reward

    Aug 5, 2025Zachary Roch, Yue WangNash Equilibrium ComputationMulti-Agent System Optimization

    Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.