# Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation

arXiv: https://arxiv.org/abs/2603.09208 · HTML: https://mlsanity.com/paper/2603.09208/

## Key facts

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

## Builds on (most cited first, 30 of 31)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Robust Autonomy Emerges from Self-Play](https://mlsanity.com/paper/2502.03349/) (2025)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [JaxMARL: Multi-Agent RL Environments and Algorithms in JAX](https://mlsanity.com/paper/2311.10090/) (2023)
- [Melting Pot 2.0](https://mlsanity.com/paper/2211.13746/) (2022)
- [RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agents](https://mlsanity.com/paper/2102.08159/) (2021)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2110.09771/) (2021)
- [RiskQ: Risk-sensitive Multi-Agent Reinforcement Learning Value Factorization](https://mlsanity.com/paper/2311.01753/) (2023)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Risk-Sensitive Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1808.04468/) (2018)
- [OvercookedV2: Rethinking Overcooked for Zero-Shot Coordination](https://mlsanity.com/paper/2503.17821/) (2025)
- [A Game-Theoretic Framework for Managing Risk in Multi-Agent Systems](https://mlsanity.com/paper/2205.15434/) (2022)
- [Risk-sensitive Inverse Reinforcement Learning via Semi- and Non-Parametric Methods](https://mlsanity.com/paper/1711.10055/) (2017)
- [Roping in Uncertainty: Robustness and Regularization in Markov Games](https://mlsanity.com/paper/2406.08847/) (2024)
- [Risk-Averse Equilibrium for Games](https://mlsanity.com/paper/2002.08414/) (2020)
- [Finite-sample Guarantees for Nash Q-learning with Linear Function Approximation](https://mlsanity.com/paper/2303.00177/) (2023)
- [Learning of Nash Equilibria in Risk-Averse Games](https://mlsanity.com/paper/2403.10399/) (2024)
- [Strategically Robust Game Theory via Optimal Transport](https://mlsanity.com/paper/2507.15325/) (2025)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economics](https://mlsanity.com/paper/2508.08669/) (2025)

## 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.