mlsanityData to 7 Oct 2026

Tractable Equilibrium Computation in Markov Games through Risk Aversion

arXiv 2406.14156 ↗First posted 20 Jun 2024cs.GT cs.LG cs.MAcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 40 of its 93 references that are in the map. First posted on arXiv 20 Jun 2024.

Builds on

40 of 93 references.

References · 40

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2013Risk-sensitive Reinforcement Learningcited by 129
  3. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  4. 2022Robust Reinforcement Learning using Offline Datacited by 95
  5. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  6. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  7. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  8. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  9. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
  10. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  11. 2021Modeling Strong and Human-Like Gameplay with KL-Regularized Searchcited by 50
  12. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
28 more
  1. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  2. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  3. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  4. 2019Reinforcement Learning for Market Making in a Multi-agent Dealer Marketcited by 35
  5. 2023Robust Multi-Agent Reinforcement Learning with State Uncertaintycited by 35
  6. 2021RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agentscited by 31
  7. 2020Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learningcited by 28
  8. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  9. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
  10. 2023RiskQ: Risk-sensitive Multi-Agent Reinforcement Learning Value Factorizationcited by 19
  11. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  12. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  13. 2022A Game-Theoretic Framework for Managing Risk in Multi-Agent Systemscited by 13
  14. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  15. 2017Fairness Incentives for Myopic Agentscited by 10
  16. 2022Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibriacited by 8
  17. 2022Risk-Sensitive Bayesian Games for Multi-Agent Reinforcement Learning under Policy Uncertaintycited by 5
  18. 2023Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibriacited by 5
  19. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  20. 2020Risk-Averse Equilibrium for Gamescited by 4
  21. 2022RASR: Risk-Averse Soft-Robust MDPs with EVaR and Entropic Riskcited by 4
  22. 2024Learning of Nash Equilibria in Risk-Averse Gamescited by 4
  23. 2017Online Monotone Gamescited by 3
  24. 2021Robust Risk-Sensitive Reinforcement Learning Agents for Trading Marketscited by 3
  25. 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
  26. 2023On the Interplay between Social Welfare and Tractability of Equilibriacited by 2
  27. 2024Learning and Calibrating Heterogeneous Bounded Rational Market Behaviour with Multi-Agent Reinforcement Learningcited by 2
  28. 2023Risk-sensitive control, single controller games and linear programmingcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2026Training Generalizable Collaborative Agents via Strategic Risk Aversioncited by 2
  2. 2025Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Gamescited by 0
  3. 2026Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learningcited by 0