Tractable Equilibrium Computation in Markov Games through Risk Aversion

2024-06-20 · Eric Mazumdar, Kishan Panaganti, Laixi Shi

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.

📄 PDF Abstract BibTeX arXiv:2406.14156

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Identification and Estimation of Dynamic Games with Unknown Information Structure

2022-05-07 · Konan Hara, Yuki Ito, Paul Koh

This paper studies the identification and estimation of dynamic games when the underlying information structure is unknown to the researcher. To tractably characterize the set of Markov perfect equilibrium predictions wh…

counterfactual

Anytime-Constrained Equilibria in Polynomial Time

2024-10-31 · Jeremy McMahan

We extend anytime constraints to the Markov game setting and the corresponding solution concept of an anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equilibria that …

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Regret Minimization and Convergence to Equilibria in General-sum Markov Games

2022-07-28 · Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren 외

An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Nevertheless, none of these results preclu…

VISER: A Tractable Solution Concept for Games with Information Asymmetry

2023-07-18 · Jeremy McMahan, Young Wu, Yudong Chen, Xiaojin Zhu 외

Many real-world games suffer from information asymmetry: one player is only aware of their own payoffs while the other player has the full game information. Examples include the critical domain of security games and adve…

Multi-agent Reinforcement Learning

The Complexity of Markov Equilibrium in Stochastic Games

2022-04-08 · Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang

We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discoun…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)