mlsanityData to 7 Oct 2026

Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation

arXiv 2603.09208 ↗First posted 10 Mar 2026cs.LG cs.GT cs.MAcited by 0

Not on the map. Why?

Abstract (arXiv)

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 textttRQRE-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 textttRQRE-OVI achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches. These results suggest textttRQRE-OVI offers a principled, scalable, and tunable path for equilibrium learning with improved robustness and generalization.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 31 of its 63 references that are in the map. First posted on arXiv 10 Mar 2026.

Builds on

31 of 63 references.

References · 31

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2023Nash Learning from Human Feedbackcited by 220
  5. 2013Risk-sensitive Reinforcement Learningcited by 129
  6. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  7. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  8. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  9. 2025Robust Autonomy Emerges from Self-Playcited by 64
  10. 2023JaxMARL: Multi-Agent RL Environments and Algorithms in JAXcited by 59
  11. 2022Melting Pot 2.0cited by 37
  12. 2021RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agentscited by 31
19 more
  1. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  2. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  3. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  4. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  5. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  6. 2023RiskQ: Risk-sensitive Multi-Agent Reinforcement Learning Value Factorizationcited by 19
  7. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  8. 2018Risk-Sensitive Generative Adversarial Imitation Learningcited by 16
  9. 2025OvercookedV2: Rethinking Overcooked for Zero-Shot Coordinationcited by 14
  10. 2022A Game-Theoretic Framework for Managing Risk in Multi-Agent Systemscited by 13
  11. 2017Risk-sensitive Inverse Reinforcement Learning via Semi- and Non-Parametric Methodscited by 12
  12. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  13. 2020Risk-Averse Equilibrium for Gamescited by 4
  14. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  15. 2024Learning of Nash Equilibria in Risk-Averse Gamescited by 4
  16. 2025Strategically Robust Game Theory via Optimal Transportcited by 4
  17. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  18. 2025Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economicscited by 2
  19. 2025Distributionally Robust Nash Equilibria via Variational Inequalitiescited by 2

Built on by

Not cited yet.