# Tractable Equilibrium Computation in Markov Games through Risk Aversion

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 40 of its 93 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Modeling Strong and Human-Like Gameplay with KL-Regularized Search](https://mlsanity.com/paper/2112.07544/) (2021)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Reinforcement Learning for Market Making in a Multi-agent Dealer Market](https://mlsanity.com/paper/1911.05892/) (2019)
- [Robust Multi-Agent Reinforcement Learning with State Uncertainty](https://mlsanity.com/paper/2307.16212/) (2023)
- [RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agents](https://mlsanity.com/paper/2102.08159/) (2021)
- [Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2004.10888/) (2020)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [RiskQ: Risk-sensitive Multi-Agent Reinforcement Learning Value Factorization](https://mlsanity.com/paper/2311.01753/) (2023)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [A Game-Theoretic Framework for Managing Risk in Multi-Agent Systems](https://mlsanity.com/paper/2205.15434/) (2022)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Fairness Incentives for Myopic Agents](https://mlsanity.com/paper/1705.02321/) (2017)
- [Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria](https://mlsanity.com/paper/2202.05446/) (2022)
- [Risk-Sensitive Bayesian Games for Multi-Agent Reinforcement Learning under Policy Uncertainty](https://mlsanity.com/paper/2203.10045/) (2022)
- [Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria](https://mlsanity.com/paper/2305.14329/) (2023)

## Built on by (most cited first, 4 of 4)

- [Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economics](https://mlsanity.com/paper/2508.08669/) (2025)
- [Training Generalizable Collaborative Agents via Strategic Risk Aversion](https://mlsanity.com/paper/2602.21515/) (2026)
- [Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Games](https://mlsanity.com/paper/2503.22779/) (2025)
- [Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning](https://mlsanity.com/paper/2602.21020/) (2026)

## Abstract (arXiv)

A significant roadblock to the development of principled multi-agent reinforcement learning is the fact that desired solution concepts like Nash equilibria may be intractable to compute. To overcome this obstacle, we take inspiration from behavioral economics and show that -- by imbuing agents with important features of human decision-making like risk aversion and bounded rationality -- a class of risk-averse quantal response equilibria (RQE) become tractable to compute in all n-player matrix and finite-horizon Markov games. In particular, we show that they emerge as the endpoint of no-regret learning in suitably adjusted versions of the games. Crucially, the class of computationally tractable RQE is independent of the underlying game structure and only depends on agents' degree of risk-aversion and bounded rationality. To validate the richness of this class of solution concepts we show that it captures peoples' patterns of play in a number of 2-player matrix games previously studied in experimental economics. Furthermore, we give a first analysis of the sample complexity of computing these equilibria in finite-horizon Markov games when one has access to a generative model and validate our findings on a simple multi-agent reinforcement learning benchmark.