Tractable Multi-Agent Reinforcement Learning through Behavioral Economics
Authors: Eric Mazumdar
Kishan Panaganti
Laixi Shi
Venue: ICLR 2025 Oral (2025)
Keywords: behavioral economics
risk-aversion
multi-agent reinforcement learning
quantal response
bounded rationality
Primary area: learning theory
TL;DR: By incorporating risk aversion and bounded rationality into agents' decision-making processes, we introduced a computationally tractable equilibria class for matrix and Markov games which aligns with observed human behaviors.

Abstract: A significant roadblock to the development of principled multi-agent reinforcement learning (MARL) algorithms is the fact that desired solution concepts like Nash equilibria may be intractable to compute. We show how one can overcome this obstacle by introducing concepts from behavioral economics into MARL. To do so, we imbue agents with two key features of human decision-making: risk aversion and bounded rationality. We show that introducing these two properties into games gives rise to a class of equilibria---risk-averse quantal response equilibria (RQE)---which are tractable to compute in \emph{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' degrees of risk-aversion and bounded rationality.  To validate the expressivity 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. We validate our findings on a simple multi-agent reinforcement learning benchmark. Our results open the doors for to the principled development of new decentralized multi-agent reinforcement learning algorithms.

Published as a conference paper at ICLR 2025
TRACTABLE MULTI-AGENT REINFORCEMENT LEARN- ING THROUGH BEHAVIORAL ECONOMICS
Eric Mazumdar', Kishan Panaganti", & Laixi Shi' Department of Computing and Mathematical Sciences California Insitute of Technology
Pasadena, CA, USA (ma maazumaar, kpb, laixis @caltech.
ABSTRACT
A significant roadblock to the development of principled multi-agent reinforcement learning (MARL) algorithms is the fact that desired solution concepts like Nash equilibria may be intractable to compute. We show how one can overcome this obstacle by introducing concepts from behavioral economics into MARL. To do so, we imbue agents with two key features of human decision-making: risk aversion and bounded rationality. We show that introducing these two properties into games gives rise to class of equilibria- gqulibbiaa-risk-averses risk-avvrre quantal response equilibria (Rih) are tractable to compute in all n-player matrix and finite-horizon Markov games. In particular, 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' degrees of risk-aversion and bounded rationality. To validate the expressivity of this class of solution concepts we show that captures peoples' patterns of play in number of 2-player matrix games previously studied 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. We validate our findings on simple multi- agent reinforcement learning benchmark. Our results open the doors for to the development of new decentralized multi-agent reinforcement learning algorithms.
show that they emerge the endpoint of no-
INTRODUCTION
Machine learning algorithms are increasingly being deployed in dynamic environments in which they interact with other agents like people or other algorithms. Often, these agents have their own goals that may not be aligned with those of the lgorritmm-makin the interactions strategic. These interactions are naturally modeled as games between rational agents and their ubiquity has driven a surge of interest in learning in games (Cesa-Bianchi and Lugosi. 2006) and multi-agent reinforcement learning (Zhang et al., 2021a) in recent years. Indeed, real-world applications of these problems range from the decentralized control of the smart grid (Mohsenian-Ran et al., 2010), autonomous driving (Kannan et al., 2017), and financial trading (Wellman and Wurman, 1998) to problems of aligning large language models (Munos al., 2024) and agentic AI (Verma al., 2024).
When viewed through the lens of game theory, many of these problems can be cast as problems of equilibrium computation under varying information structures, where the equilibrium represents a stable outcome for rational agents. The most common equilibrium concept is that of a Nash cquilibrium (NE) (Nash, 1950): solution under which no rational agent has an incentive to unilater- ally seek to improve their outcome. Despite its popularity as a solution concept, computing NE outside of highly structured games known to be computationally intractable even for two-player matrix games (Daskalakis, 2013). Coupled with a host of negative results on their computation using gradient-based algorithms (Mertikopoulos et al., 2018; Mazumdar al., 2020), converging to Nash increasingly viewed unreasonable goal for decentralized reinforcement learning algorithms.
Alphhhettccal order.

---

Published as a conference paper at ICLR 2025
While relaxations of NE like (coarse) correlated equilibria (CCE) are known to be more tractable to compute-au and thus a more attainable goal for learning algorithms- they also have their limitations. Indeed, while CCE arise out of the use of no-regret learning algorithms (Cesa-Bianch) Bianchi and Lugosi, 2006), the set of CCE can be large (exacerbating the problem of equilibrium selection that arises with NE) and may have support on strictly dominated strategies (Viossat and Zapechelnyuk, 2013), which means that they cannot necessarily be rationalized by individual agents in isolation (Dekel and Fudenberg, 1990). Furthermore, a dynamic versions of CCt-stationary Markov CCE-can also be intractable to compute in general-sum Markov games (Daskalakis et al., 2023b).
Beyond these hardness results, solution concepts like NE and CCE also fail to be predictive of what strategies people play in games (McKelvey and Palfrey, 1995; Erev and Roth, 1998), with people being observed to be imperfect optimizers (Goeree and Holt, 1999; Capra et al., 2002) and risk-averse (Goeree et al., 2003) when confronted with game theoretic scenarios. This aligns with celebrated work in behavioral economics and mathematical psychology which has repeatedly shown that dominant features of human decision-making are failure to perfectly optimize (Luce, 1959) and risk-aversion (Kahneman and Tversky, 1979; Tversky and Kahneman, 1992).
The first observation is often referred to as bounded rationality which posits that individuals are naturally prone to making mistakes and often fail to be perfectly optimal (Luce, 1959). This is often captured in games through the idea of quantal response equilibrium (QRE) (McKelvey and Palfrey, 1995). The second observation can be attributed to the fact that players typically face uncertainty and risk in their decisions. These arise from environmental uncertainties like unknown future events, noise, or even the mere presence of other players. This can lead people to prefer risk-averse strategies, i.e., strategies which give more certain outcomes the cost of lower expected returns (Gollier, 2001). Interestingly, there is experimental evidence that neither of these properties alone can account for people's patterns of play observed in controlled experiments (Goeree et al., 2003; Goeree and Offerman, 2002), and that models of decision- decision-making that incorporate both of these features have the best predictive power (Goeree et al., 2003).
Motivated by these findings, in this paper we study games in which players are risk- averse and have bounded rationality and study the computational properties of the natural equilibrium concept: a risk-averse quantal response equilibrium (RQE). At first glance, the introduction of these features of human decision-making into games introduces non-linearities that break existing game- theoretic structures. Indeed we show how neither of these features alone give rise to single class of equilibria that can efficiently computed across all games. However, by relying on dual formulations of risk we show how-for large range of degrees of risk-aversion and bounded rationality- class of RQE are computationally tractable in all n-player matrix and finite horizon Markov games. Importantly, these conditions are independent of the underlying game and only depend on the class of risk metrics and quantal responses under consideration. Thus, RQE not only capture important features of human decision-making but are also more amenable to computation than QRE or NE in matrix and finite-horizon Markov games. This opens the door for the development of theoretically principled decentralized algorithms for multi-agent reinforcement learning (MARL) centered around RQE as opposed to CCE or NE, We refer readers to the discussion of related works in Appendix A for a more in-depth discussion of different equilibria concepts in the context for our work.
Contributions:
To emphasize the practical relevance of this theoretical result we show how the regime for which RQE are computationally tractable captures real-world data from behavioral economics on people's observed pattern of play in 13 different games. This is illustrated in Fig. 1, where the blue region represents the set of RQE that are computationally tractable which is a function of agents' degree of risk- /22), and level of bounded rationality (c1/c2).
Altogether, our results show that imbuing artificial agents with features of human decision -aking from behavioral economics gives rise to expressive class of equilibria in games. Crucially, this new solution concept appears to overcome many of the computational limitations of existing concepts and thus appears to be promising foundation for the development of principled MARL algorithms.
Notations: We use An to denote probability simplex of size n. In addition, we denote [N] = (1,2.... ,N} for any positive integer N > O. We denote x = [a((s, a)] (s.a)exxA E SA (resp. x
[n(s)] EES E 5R as any vector that constitutes certain values for each state-action pair (resp. state).
2

---

Published as a conference paper at ICLR 2025
Penalty Function: vergence (Entropic Risk)
Penalty Function: Reverse KL Divergence
Regubrrizer: Barrier
Regularizer: Negarive Entropy
GHI: Game
SC Game
Game
SC. Game
20
SC Game
Game
15
36
SC: Game
SC Game
Game
20-
Game
0.02 0.04
0.06
0.08
0.10
0.12
0.24
0.15
0.8 2.0
f1
C17)
Figure The shaded blue region depicts the regime of risk aversinn and bounded rationality preferences that allow for computationally tractable RQE in all 2-player games as shown in Theorem 3. The markers GHP: Game 4 (Goeree al., 2003) and SC: Game 1-12 (Selten and Chmura, 2008) represent the necessary parameter values required to recreate the average strategy played by people in various 2-player games observational data up to 1% accuracy.
AVEK-AVERSION AND BOUNDED RATIONALITY IN GAMES
To begin, we focus on rl-layer general- sum finite-actin games. In these games, each player has access to a (finite) action set A, with A; |A, pure strategies. For each tuple of joint strategies = (A1, ...: (n)) A IT. A; each player has an associated reward or utility (a). As is common in the study of these games, and seek to maximize their expected utility. Player i's expected utility in this case can written as function U; - R which can be written as:
sum
consider the case where players play over mixed strategies
Ue(TI, .. Tn) (Ra=n[Ri(a)
where
Tn) p= IT AA, is the joint strategy of all the players. For case of exposition we often write the utility as (TT, T-;) where π-ं = (T) Ti-1, 1 T.) represents the joint strategies of all players other than i. A natural outcome in this class of games is the notion (mixed) Nash equilibrium.
Definition (Nash Equilibrium). (mixed) Nash equilibrium of n-player general-sum finite-action game is a joint strategy nt = (Ti.... ..., The E P such that no player has any incentive to unilaterally deviate-ie...ff all ..., ( T (T; x".)) VT; E A
As introduced, n-player general-sum finite-action games are well known to admit at least one Nash equilibrium (NE) in mixed strategies (Nash, 1951). While NE are known to always the exist in mixed strategies in the games we consider, they have also been shown to be intractable to compute (Daskalakis, 2013). Moreover, NE may not realistically predict human decision-making behavior. Indeed preponderance of empirical evidence suggests that people do not play their Nash strategies and in fact are potentially bounded rational and risk-averse their decision decision-making inducing forms of equilibria (see e.g., Luce (1959): Tversky and Kahneman (1992); Goeree et al. (2003); McKelvey and Palfrey (1995)). To formally introduce these features of human decision- making the problem, we construct generalizations of the expected utility game that allow model agents as either imperfect optimizers and risk-averse.
2.1 BOUNDED RATIONALITY IN GAMES
In contrast to risk-aversion, which has been under-explored in game theory and multi-agent rein- forcement learning, bounded rationality is more common. Many works studying the computational benefits of incorporating it into games (Sokota et al., 2023; Mertikopoulos and Sandholm, 2016; Cen et al., 2021; Leonardos et al., 2021; Evans and Ganesh, 2024; Jacob et al., 2022), with the most common form of bounded rationality found the literature on learning in games being that a quantal response. These capture bounded rationality by either assuming that the players are rational in a stochastically perturbed version of the game or equivalently that players' strategies are constrained to the set of quantal response functions (McKelvey and Palfrey, 1995; 1998).
3

---

Published as a conference paper at ICLR 2025
Definition 2. (Quantal Response Function) A quantal response function is continuous function a: R" + An such that for any x E R": xf, < Ij, o,(x) > oz(x), where 2k, (x) represent the k-th components of z and respectively.
These functions restrict players' strategies to subsets of the simplex effeecivlily smoothing their best responses and preventing them from being complete utility maximizers. One way to restrict player's 's strategy to quantal responses is by regularizing their objectíve with a suitable strongly convex regularizer v (see, c.g., Föllmer and Schied (2002, Proposition 7), or Sokota et al. (2023); Mertikopoulos and Sandholm (2016)). This yields adjusted utility functions of the form:
U (TI...., Tn) = Eawn [a) - (.((),)
where 6 2 captures player i's degree of bounded rationality. As 6, increases their strategy space becomes more constrained, yielding more boundedly rational strategies. When all players achieve a Nash equilibrium in the space of their quantal responses-tth class of strategies that can be represented by fixed class of quantal response functions (cf. Definition 2h resulting equilibrium known as a quantal response equilibrium (QRE).
Despite the many works that focus computing QRE, to the best of our knowledge there are no classes of QRE that are universally computable across all games. Indeed most works focus on zero-sum or approximately zero-sum games (Sokota et al., 2023; Mertikopoulos and Sandholm, 2016; Leonardos et al., 2021). In more general classes of games the class of QRE or equivalently the level of bounded rationality needed for computational tractability depends structure (e.g., the size of player's ' action spaces and the magnitude of their rewards) which may not be known priori (Sun et al., 2024). Furthermore, we note that more work in behavioral economics has consistently highlighted that bounded rationality on its own is not enough to capture the nuances of human Tversky and Kahneman, 1992). These findings motivate us to introduce risk-aversion into games.
the underlying game
even for simple games such as matching pennies (Goeree al., 2003;
2.2 RISK-AVERSION IN GAMES
To allow agents to have risk preferences we make use of a general class of convex risk metrics from mathematical finance and operations research (Föllmer and Schied, 2002). In this framing we move into a regime where agents seek to minimize a measure of risk.
Definition 3 (Convex Risk Measures). Let X be the set of functions mapping from a spuce of outcomes Ω to R. A convex measure of risk is mapping p:: X + R satisfying:
1. Monotonicity: If X < Y almost surely, then p(X) 2 p(Y).
2. Translation Invariance: If m E R then p(X + m) p(X)
3. Convexity: For all X E (0, 1), p(AX + (1 S Xp(X) + (1 A)P(Y).
Typically, and as we assume in the remainder of the paper, the set X' the set of measurable functions defined on probability space (S,F, P). Under this assumption, the convex measures of risk allow us to generalize expectations to trade off high variance for and higher utilities. For ease of exposition, we write Px (X) to highlight the distribution that the convex risk measure is taken with respect to
Given these definitions, we present two ways of incorporating risk-aversion into games. Remark 1. A crucial feature of our formulation of avsk-aversion is that players are not risk-averse to the randomness introduced by their own strategy and only to the uncertainty caused by the environment and their opponents. This is a common approach taken (often implicitly) in the literature on single-agent risk-sensitive and robust decision-making (Shen et al., 2014). It also appears to be necessary to ensure the existence of equilibria introduced in Theorem shortly; otherwise as studied in Fiat and Papadimitriou (2010), equilibria may not exist.
To see why our framing of risk aversion natural we introduce the first form of risk that we consider: action- derended risk- aive-iversion.
Action -eteon-de Risk Aversion: this framing, a player first evaluates the risk associated with each of their pure strategies az: ,- (R(a,, a-;). The player then minimizes their expected risk. We capture this by transforming the player's ''s utilities in (1) into costs foet of the form:
fact (IT π -;) En, [Pi.F_, (R.(a)) = EaJe mi(a:)i.... (Ra a-)))
(3)
4

---

Published as a conference paper at ICLR 2025
where Pt, is used to capture agent i's risk preference which depends on the product distribution of opponents strategies --
Under action-dependent risk-aversion player uses mixed strategies only when two pure strategies yield the same level of risk. Thus introducing additional risk-aversion to n; does not change outcomes.
we consider, aggregate risk-aversion is more conservative, but allows for a simpler analysis. To capture aggregate risk aversion, we transform the player's 's utilities in (1) into costs fe which take the form
Aggregate Risk Aversion:
The second form of
f f (T,, T-1) Pi,x_, (L.,, [a)) = Pi (E,,Es, Ra,
Aggregate svs-svversoon captures the fact that risks may be correlated across pure strategies, and is related (due to convexity of p:) by Jensen's inequality to action dettonddeeendent risk-aversion such that < f.a((T)) (T). Interestingly, recent work in behavioral economics has shown that this may be a better model of risk-aversion in people (Oprea and Robalino, 2024).
We note that if pc(X) = E for all players = 1,.... n (which satisfies the requirements in Definition 3), then the new formulations reduce to the original expected utility objective. Thus, the class of risk-averse games can be seen as generalizations of the classic expected utility games (1). Remark 2. For brevity, as both generalizations have similar implications, we provide details and results of action-dependent risk aversion in our supplementary material and focus on aggregate risk aversion for the remainder of the paper. Thus we denote fa = 5, for the remainder of the paper and analyze fi = f in the supplementary material.
While at first glance the modified game looks significantly more complex than the previous expected utility maximization setup (cf. (I)), can rely particularly powerful property of convex measures risk to simplify and expose some structure in this class of problems.
Theorem (Dual Representation Theorem for Convex Risk Measures (Föllmer and Schied, 2002)). Suppose that the set X is the set of functions mapping from finite set Q to R. Then a mapping X TR. is a convex risk measure (cf. Definition 3) if and only if there exists penalty function D An - (-o0, 20] such that: p(X) = suppE Epl-X] - Dp), where Da is the set of all probability measures on Ω. Furthermore, the function D(p) can be taken to be convex, lower-semi- continuous, and satisfy D(y)= > -0) for all p E An.
Throughout, make a simplifying assumption that D is continuous in both arguments, which is satisfied by various widely used risk measures Table 1. We provide more details on penalty functions in Appendix B. Given this result, we derive the aggregate risk-averse game (4) in the following form:
fA T-I)
sup 7. Rap: D.(pp, MEP-
m Vi vi=I...,. n,
Ti
where P-, P-:=P/AA C CRA,,
y Aj. and R. E ERA.A- is player i's payoff matrix.
We note that we differentiate the penalty functions D; to allow agents to have different risk preferences in different risk metrics. The parameter Ty captures player's degree of risk-aversion. In this form, one can see that in a risk-averse game, the players imagine that intermediate adversaries seek to maximize their cost but are penalized from deviating too far from the opponents' realized strategies. As :; + oc they become increasingly risk-averse and in the extreme, treat their opponents and environment as adversarial.
Since a NE of the risk-averse game can be qualitatively different from that of the original game, we now define risk-averse Nash equilibrium (RNE). For brevity, we do not introduce aggregate and action-dependent RNE separately, since similar results hold for either formulation.
Definition 4. (Risk-Averse Nash Equilibrium) A risk-averse Nash equilibrium (RNE) of is joint strategy n² P such that no player has any incentive unilaterally deviate in the risk adjusted game-i.e., for all i = 1,..., n2: fa(m;
(/m.mT=i) T²x) S f((TT, V Ti E AA.
Note that since players would like to minimize risk, the direction of the inequality has changed. The convexity and continuity of the penalty function guarantees that the risk-averse games admit at least one RNE, A general statement and proof are provided in Theorem
Theorem 2. All aggregate risk-averse games (5) admit at least one RNE.
5

---

Published as a conference paper at ICLR 2025
The existence of RNE is consequence of the fact that under risk formulations, players risk averse to the randomness of their own by playing a mixed strategy. This is in stark contrast to previous works which consider games in which players are risk-averse to all randomness (including their own), and in which a RNE may not exist (Fiat and Papadimitrion, 2010). Thus, our specific risk formulations crucial
later results.
Finally, we note that the additional convexity induced by the introduction of risk aversion guarantee not enough ensure the computational tractability of the risk-averse Nash equilibrium (see e.g.. (McMahan et al., 2024)). This is not surprising given the fact that computing NE in general convex games can be intractable in general.
3 RISK-AVERSE QUANTAL RESPONSE EQUILIBRIA IN MATRIX GAMES
Since neither bounded rationality nor risk-aversion alone guarantees computational tractability of their associated solution concepts, we consider the equilibrium concept that arises out of their combination and show that it can often be efficiently computed. Interestingly, this echoes work in behavioral economics in which the combination of risk aversion and bounded rationality has also been found to be a better predictor human play (Goeree et al., 2003) than either of the properties alone.
Towards this goal, in the final form of the risk-adjusted game we consider, players' costs are given by:
(T, -) = [T,, -): ( (T:) Vi 1,..,
(6)
where v4 strictly convex regularizer which gives rise to a set of quantal responses. The natural outcome of this game is what we term as risk-averse
equilibrium (RQE).
Definition 5 (Risk-Averse Quantal Response Equilibrium (RQE)), A risk-averse quantal response equilibrium of a n-player general-sum finite-action game is a joint strategy n² E such that for each player I.
(T) + f Te. E
For any set of convex regularizers v4, it is easy to observe that the game remains a convex game and thus RQE (as defined) will always exist in all matrix games.
3.1 CONDITIONS FOR THE COMPUTATIONAL TRACTABILITY OF RQE
Given our definition RQE, we now demonstrate that players' risk preferences (i.c., their degree of risk aversion) and families of quantal response functions (i.e., their bounded rationality parameters) satisfy a simple relationship, the game admits a RQE that can be efficiently computed using arbitrary no-regret learning algorithms (e.g.. gradient-play Importantly this result is independent of the underlying payoffs {R:
mirror descent) in decentralized manner.
To derive our results on the computational tractability of RQE under aggregate risk-aversion, first introduce a related 2n-player game in which we associate to each original player i an adversary whose strategy is denoted as p. P_,. Let p (PI, ... E P II P_t. In this new game, each original player's 's loss function takes the form:
J. (TTTTTT.P)) = - R.p: - Di(p,, T-1) + (..)
For each player p; we associate them to a new loss function which we denote:
J(TT = 7, R.p, + - Di(p, - (esus(TTT).
(8)
J#1
In this 2n player game, the i-th player's 's adversary. whose strategy is pt seeks to minimize their loss Jj which is strategically the same maximizing J,.
Given the definition of the 2n-player game we show how no-regret learning algorithms can be used to compute RQE. To prove this, first define coarse correlated equilibria (CCH).

---

Published as a conference paper at ICLR 2025
Definition 6. A coarse correlated equilibrium of the 2n-player game is probability measure P x P such that for all i = 1,,, 71,
(s [Ja(T,, p)] I E (x- Je( -.. :>>a
Vn E A.. [x [T p)] < :)>a (J. Vpi P_;.
CCE are the natural outcome of no-regret learning algorithms, and we show that CCEs of the 2n- player game coincide with ROE of the original n-player matrix game. This is a phenomenon known as equilibrium collapse which is well known to happen in zero-sum games and certain generalizations of zero-sum games (Cai et al., 2016; Kalogiannis and Panageas, 2023). For brevity we present our results on 2-player matrix games now and extend the results to n-player setting in Appendix C.3.
To simplify our results we define (PI, T2) = 1 D1,,, m2) ( and H2(p2, TT)
Ti
1 D2(p2, ) - (TT)) Let či > 0 and E > 0 be the smallest values of & and & such that (P1: x2) and (2(2,, æ1) are concave in and иı for all p1 and p2 respectively. These parameters capture the player's relative degrees of risk aversion, and as we show, for certain instantiations of risk measures and quantal response functions &
for i = 1,2. The following theorem gives conditions on Ei. E and é1; f2, under which RQEs can be computed through no-regret learning. The proof postponed Appendix C.2.
Theorem 3. Assume the penalty functions that give rise to the players' risk preferences Di(::)) and -2( are jointly convex in both their arguments. If a is CCE the four player game with $1 = Ei and E2, = Eg and 6162 2 Ei52, then म = [ and îं2 [T]] constitute an ROE of the risk-averse game.
This theorem gives a range of risk aversion and bounded rationality parameters under which an RQE can be computationally tractable using no-regret learning. This range is independent of the structure in the underlying mame-making the class of tractably computable equilibria universal to all games. In the case where ; = +. we observe that for any é1. c1 > 0, as T; - oc, the game becomes solvable. This captures the fact that for any degree of bounded rationality one can compute players' security strategy using no-regret tractability of min-max strategies.
existing results on the computational
To validate this result, we show that the class of computationally tractable RQE is sufficiently rich to capture the aggregate strategies played by people in matrix games studied in laboratory experiments in behavioral economics to showcase how human behavior can differ from Nash equilibrium strate- gies (Selfridge, 1989; Goeree al., 2003; Selten and Chmura, 2008). In particular, we showcase in Fig. 1 that for some choice of parameters (c and Ty 's) satisfying conditions in Theorem 3, we recover human behaviors in various matching pennies games investigated in Tables and We provide more details about the games and experiments in Appendix F.I.
4 RISK-AVERSE QUANTAL RESPONSE EQUILIBRIA IN MARKOV GAMES
In this section, we extend our results to finite-horizon Markov games, or stochastic games (Shapley, 1953) which allow to model dynamic games played out over Markov decision processes (MDP).
A Markov game can be seen as a sequential matrix game with stochastic dynamics. In this paper. consider general-sun sum (H,S, (A:)) Ra,,, hesm)).es
Markov games involving players, represented as Mÿ Here, H is the time horizon length of the Markov game and S = {1, ... ,}} represents the state space of the underlying MDP with size S. We also adopt the same notation in Section 2, and let (A,) represent the action spaces of each player, each with cardinality |A,| A,. Similarly, the joint action space is given by A, joint action profile is a E A, and P the product policy space. Similarly, Rich represents the utility or reward function of the i-th player time step h for any hi) E [m] [H] and Ra (s, a) represents the immediate reward (or utility) received by the i-th player given state-action pair (s, a). For simplicity, we assume R.A. is deterministie. Lastly, the dynamics are captured by transition kernels P.A. S x A H Ag where P s, a) which capture probability transitioning from current state s to the next state s' conditioned on the joint action a.
Markoy policies and value functions. In the classical setup of finite-horizon Markov games, players are assumed play over the space of Markov policies, where at any state at any time
7

---

Published as a conference paper at ICLR 2025
step h [H], the action selection rule depends only on the current state s, and is independent of previous trajectories and other players. Specifically, the i-th player or agent executes actions according to policy x; {TEA S + A., highgt. with the probability of selecting action in state 8 at time step h given by Ti,n {a 8). Since we are operating in a finite horizon regime, is natural to assume the policies are time-dependent. For simplicity, we define the joint policy of all agents as product policy defined as π (TI...., Tx) S x [H] + P and the joint policy space as I1. As such, the joint action profile a of all agents is drawn from distribution specified by
T s) = (T1,h, T2.h A- s) E P conditioned on state at time step h. For any given n,
we employ -=. : S x H H P- to represent the policies of all agents excluding the i-th agent.
4.1 RISK-AVERSE MARKOV GAMES
Given these definitions, we now generalize Markov games by allowing agents to be risk-averse to both the uncertainties arising from other agents' strategies and from the stochastic dynamics. This results in a new formulation of risk-averse Markov games (RAMGs). To address the two sources of risk-aversion we allow agents to have different risk preferences for their opponents and for the environment. To do so we fix two penalty functions (t. (e))) and (Denv.(:--))aeenn which in turn give rise to two risk metrics. This allows us to define the following two functions which separately capture the risk associated with other players' actions and the environment respectively:
E [m]: (Qi) = sup - -- Q.P. i T-1);
M.P::
Vi [n]:
= inf PEAs
R + PV + Denv. (P, P1].
for any joint policy ग, where Qi RAIXEIIA R E E cumulative payoff matrices and P E As, represents the dynamics of the MDP. Note that for simplicity, we choose the same (veol.tivenn) and (Denv.llie(n) for all time steps h E [H], though this can be considered to be time dependent as well.
RS will be used to represent
Given the definition of these two penalty functionn (+) and f.)v,(()), we can now define an agent's 's cumulative risk in a RAMG. For risk-averse agent i their goal is now to minimize their own long-term risk, which can be captured by risk-averse value function (e)(M))) where (T, S IR for any joint strategy и E II. This can be defined recursively as follows: for a given joint policy ग,, for all (h, s) E [H] X S,
VA, 8) Spol. (Qi,N(T;
(10)
where Qi, 8, a) = Senu.s a)) Pr.,,as Ve,b+1 (T)) and Pr.s,a Pa.. 8, a) E RIIS.
To parse this definition, we observe that Qi (TT; s.:) E A As represents a payoff matrix for the i-th player at state and time step h, where the value at the a;-th row and the a- column is specified by Qi, (IT; s, a) with a = (a;, a-i) which captures an agents' cumulative risk if joint action a is executed at state s and time h, and the policy æ is followed subsequently. This can also be captured concisely through a recursive definition:
Vi,a (T; 8) = fpol. o Senv.s (R.,n Ph...: [Splls Senu. ( Patt, I])
We remark that this definition reduces to the classical setup of multi-agent reinforcement learn- ing (Zhang et al., 2021a) when agents are nesk-nl and to the well studied setup of risk-sensitive reinforcement learning (Shen et al., 2014) when there is only one agent.
As before, we focus on the computation of risk-averse quantal response equilibria in Markov games. To do, we constrain players to quantal responses by regularizing their value functions follows:
V(i, s) E [n] x [H] x SS: V[A s) = Ve,((T: s) + (T,).
(11)
where {& 2 0) capture players' degrees of bounded rationality. To define Markov RQE we denote - := 1e..:,,,,.....AA..bbbb
.H as agent i's policy over all times other than h. Definition 7 (Markov RQE). A product policy = x x Tn quantal response equilibrium of RAMG if:
II is said to be a risk-averse
v(i,s,h) E [m] x S [H):
(T)()))) S min
V (lTht T., ns) hn) {11is), (12)
x S-A.
where v.()) is strictly convex function over the simplex.
8

---

Published as a conference paper at ICLR 2025
4.2 COMPUTING AND APPROXIMATING MARKOV RQE
Given our setup we now investigate how to compute Markov RQE, both with full information over the dynamies and rewards and without. For the full-information regime we propose a modified form of dynamic programming, in which work backwards from time h H and then recursively compute the RQE until step h = 0. Towards this goal, at each time step h. for all (i, h, 8, a) E [n] x [H] XS X.A construct the payoff matrices for the underlying for all agents at any state
time step h as
PV. + Denu, Ph. (13) Vi,,,, E [n] x S x [H] (s,(ssa) (s, + inf PEAs
These payoff matrices capture both the future payoff's well as the risk associated with the stochastic transitions the MDP associated with a joint action a. Together, they define a matrix game at state 8 and time h, for which the routine for computing a RQE of a matrix game as RQE(-). Proceeding recursively, we compute the RQE time + 1 and use the resulting policies define the underlying payoff matrices at time We summarize the algorithm for computing Markov RQE in Algorithm in the appendix. The following theorem guarantees that the procedure will output a Markov RQE.
compute RQE using the results presented in Section 2. We denote
Theorem 4. For any RAMG MG, assume the penalty functions that give rise to the players' risk preferences {Dpola((. }} are jointly convex in both of their arguments. If. for all (s,h) E S x [H], & 2 EjttS Ej for all (i.j) E [n] x [nl,, where Ei is defined as in Theorem 9 for given (..). and Vj, then the output policy गे from Algorithm is a Markov ROE of MG.
consequence of this result is that class of Markov RQE are computationally tractable to compute via no-regret learning in umite-horizon Markov games. We remark that this is in stark contrast to both Markov Nash equilibria and Markov quantal response equilibria which cannot efficiently be computed in general-sum Markov games (Daskalakis et al., 2023b).
Computing Markov RQE in unknown Markoy Games. The previous results focused on the case when the dynamics and rewards of the RAMG are known. In practice, especially in multi-agent reinforcement learning, the environments can be complex and unknown and must be learned by interacting with (i.e., sampling from) the environments. In this subsection, focus on such scenarios and provide the theoretical guarantees for Algorithm 1.
We focus fundamental problem setup which assumes access to generative model a simulator (Kearns and Singh, 1998; Agarwal et al., 2020). This allows us to collect N independent samples for each state-action pair generated based on the true environment {Ra,, Pr. Pa)vetn),eE(1)
(s, j. S Ax [n]: $1,5,a.h bid a)),
rd r)aa,, Ry,((s,). ie [N]. (14)
The total sample size is, therefore, Nan == INIIl A..
For problems we propose model-based approach the computation of Markov RQE which first constructs an empirical reward function and nominal transition kernel based on the collected samples and then applies Algorithm I to learn a Markov RQE. First, the empirical reward function and transition kernel P ST AiXS are constructed from the empirical frequency of state transitions,
((,,,,,M) (3,(5, 7 Thaa and P 88 a)
1 = = (15)
Then with such empirical reward and transition, we can apply the oracle summarized in Algorithm 1 compute Markov RQE using model-based MARL. The following theorem provides the first finite-sample guarantees for the computation or Markov RQF.
Theorem 5. For any RAMG MG, we consider penalty functions (Demua(ts)) (().:)))) hiejn) are L-Lipschitz w.n. the & norm of the second argument with any fixed first argument. Applying Algorithm I with the estimated reward { (R and transition kernels {Ph (h))ee as input, the output solution To is an
RQE MG. Namely, we have max
{ V (T;; -0mnm ming ViS (TT R

---

Published as a conference paper at ICLR 2025
4gl Gee
Grl
50
190
100 200
Figure 2: Cliff Walk Description and Results: The Cliff Walk grid-world is depicted here with color codes of grids: black the cliff, blue and pink are agents/players and 2's goals respectively. The agents' proximity one another increases the randomness in the dynamics making falling into one of the cliff states more likely. Agent 2's policy in the left figure showcases more risk-aversion and less bounded rationality than on the right.
{- I 5 as long as the total number of samples satisfies
Nai NS II A. 2 88
II AHL VE(n]
log (2SH II A/6)) iE(m)
iE(m)
The proof is postponed to Appendix E. We remark that L can be some constant for various penalty function, such as when a are defined any lp norm including total variation (TV). We also note that our result suffers from what is known as the curse of mutliagency (Bai et al., 2020) through the dependence on []. Aj.
4.3 EXPERIMENTS AND EVALUATION
We consider a grid-world problem to test our algorithm (Algorithm 1) and showcase the effects of risk-aversion and bounded rationality in games.
Cliff Walk Environment description: A grid consists some tiles representing a cliff where they will remain stuck for all time and goal states for agents as well as goal states of agents. The cliff is the black grid with rewards 22 Agents/players are rewarded for taking each step and their respective goals. Agents actions are /up.down.left.righll
reaching and they are followed with probability Pa = 0.9 with random movements happening otherwise. To introduce multi-agent effects we reduce Pa to 0.5 when the agents at least grid cell apart- making the likelihood of falling into the cliff higher. The episode horizon H 200 and the joint state space is the tuple of players' positions.
Results Discussion: We present two results in Fig. 2. For both results, agent starts at the 5th row and 3rd column of the cliff walking groldworld, and agent starts at the 2nd row and 3rd column grid position. In both figures, the red and blue paths depict the maximum likelihood paths taken by agents and 2 respectively. Agent 2's policy in the left figure showcases more risk-aversion and less bounded rationality resulting in them preferring to hide far from obstacles than the risk of falling off the path. On the right, agent 2 successfully reaches their goal. The equilibrium strategy of agent 1 changes in both scenarios: a more risk-seeke seeking agent 2 forces agent l-in an effort to minimize risk to wait until the path is clear to attempt the journey to its goal.
5 CONCLUSION
By incorporating risk aversion and bounded rationality into agents' decision-making processes, we introduced new class of equilibria for matrix games and finite-horizon Markov games: RQE. RQE were shown to align well with observed human behavior and we provided theoretical results showing that classes of RQE tractably computable in all finite horizon Markov games. We also provided sample complexity results in the generative modeling setting for multi-agent reinforcement learning. Altogether, results open the doors to the principled development of new MARL algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
The work of LS is supported in part by the Resnick Institute and Computing, Data, and Society Postdoctoral Fellowship at California Institute of Technology. KP acknowledges support from the 'PIMCO Postdoctoral Fellow in Data Science' fellowship at the California Institute of Technology. EM acknowledges support from NSF Award 2240110.
REFERENCES
A. Agarwal, S. Kakade, and L. Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
A. Ahmadi-Javid. Entropic value-at-risk: A new coherent risk measure. Journal of Optimization
Theory and Applications, 155:1105-1121 2012. 19, 20
Auer, Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008. 28
R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974. 16
R. J. Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica, 55(1): 1-18, 1987. 16
Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play. Advances in neural
information processing systems, 33:2159-2170, 2020. 10
T. Basar. Nash equilibria of risk-sensitive nonlinear stochastic differential games. Journal of Optimization Theory and Applications, 100(3):479-495 1999. 17, 18
A. Beck. First-order methods in optimization. SIAM, 2017.
Blanchet, M. Lu, T. Zhang, and H. Zhong. Double pessimism is provably efficient for distribution- ally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
V. Borkar. Risk-sensitive control, single controller games and linear programming. Journal of Dynamics and Games, 11, 01 2023. 17, 19
N. Brown and R. Rosenthal. Testing the minimax hypothesis: re-examination of o" neilll'ss game experiment. Econometrica, 58(5): 1065-81, 1990. 17
Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou. Zero-sum polymatrix games: A general- ization of minmax. Mathematics of Operations Research, 41(2):648 655, 2016. 7, 16
C. M. Capra, K. Goeree, R. Gomez, and C. A. Holt. Learning and noisy equilibrium behavior in an experimental study of imperfect price competition. International Economic Review, 43(3): 613-636, 2002.
S. Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952-27964, 2021. 3, 17
N.
and G. Lugosi. Prediction, learning, and gamex. Cambridge University Press, 2006.
ISBN 978-0-511-5469211 1, 16
C. Daskalakis. On the complexity of approximating nash equilibrium. ACM Transactions on Algorithms (TALG), 933:1133,, 2013. 1,3,
C. Daskalakis, N. Golowich, N. Haghtalab, and A. Shetty. Smooth nash equilibria: Algorithms and complexity. arXiv preprint arXiv:2309. 2023a. 16
C. Daskalakis, N. Golowich, and K. Zhang. The complexity of markov equilibrium in stochastic games. In G. Neu and L. Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1180-42344 PMLR, 12-15 Jul 2023b. 2, 9, 16
11

---

Published as a conference paper at ICLR 2025
E. Dekel and D. Fudenberg. Rational behavior with payoff uncertainty. Journal of Economic Theory, 52(2):243-267, 1990.
I. Erev and A. Roth. Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review, 88(4):848 81, 1998. 17
H. Eriksson, D. Basu, M. Alibeigi, and C. Dimitrakakis. Risk-sensitive bayesian games for multi- agent reinforcement learning under policy uncertainty. arXiv preprint arXiv:2203. 2022.
17
B. P. Evans and S. Ganesh. Learning and calibrating heterogeneous bounded rational market behaviour with multi-agent reinforcement learning. arXiv preprint arXiv:2402.00787, 2024. 3, 17
E. Even-Dar, Y. Mansour, and U. Nadav. On the convergence regret minimization dynamics in concave games. In Proceedings of the forty-firs anmual ACM symposium on Theory of computing, pages 523-532, 2009. 16
A. Fiat and C. Papadimitriou. When the players are not expectation maximizers. In Algorithmic Game Theory: Third International Symposium, SAGT 2010, Athens, Greece, October 18-20, 2010. Proceedings pages 1-14. Springer, 2010. 4, 6, 16,
H. Föllmer and A. Schied. Convex measures of risk and trading constraints. Finance and Stochastics, 6(4):429-447, 2002. 4, 5, 19, 20
S. Ganesh, N. Vadori, M. Xu, H. Zheng, P. Reddy, and M. Veloso. Reinforcement learning for market making in a multi-agent dealer market. Advances in Neural Information Processing Systems, 2019. 17
Y. Gao, K. Y. C. Lui, and P. Hernandez-Leal. Robust tisk-sensine reinforcement learning agents for trading markets. arXiv preprint arXiv:2 107.08888 2021. 17
I. M. Gemp and S. Mahadevan. Online monotone games. ArXiv, abs/1710.073288, 2017. 23
J. K. Goeree and C. A. Holt. Stochastic game theory: For playing games, not just for doing theory. Proceedings of the National Academy of Sciences, 96(19:10564410550 1999. 2
J. K. Goeree, C. A. Holt, and T. R. Palfrey. Risk averse behavior in generalized matching pennies games. Games and Economic Behavior, 45(1):97-113, 2003. 2, 3, 4, 6, 7, 17, 30
K. Goeree and T. Offerman. Efficiency in auctions with private and common values: An experimental study. American Economic Review, 92(3):625 643, June 2002. 2, 17
C. Gollier. The economics of risk and time. MIT press, 2001.
N. Golowich. S. Pattathil, and C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Advances in neural information processing systems, 13:20766-20778, 2020. 16
He, Han, S. Su, Han, S. Zou, and Miao. Robust multi agent reinforcement learning with
state uncertainty. Transactions Machine Learning Research, 2023. ISSN 2835-8856. 18
T. Ho, C. Camerer, and J.-K. Chong. A cognitive hierarchy model games. The Quarterly Journal of Economics, 119:861-898, 2004. 17
G. N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280. 2005. 17
A. P. Jacob, J. Wu, G. Farina, A. Lerer, H. Hu, A. Bakhtin, J. Andreas, and N. Brown. Modeling strong and human-like gameplay with kl-regularized search. In International Conference on Machine Learning, pages 9695-9728. PMLR. 2022. 3, 17
D. Jacobson. Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games. IEEE Transactions on Automatic Control, 18(2): 124-131, 1973. 17
12

---

Published as a conference paper at ICLR 2025
D. Kahneman and A. Tversky. Prospect theory: An analysis of decision under risk. Econometrica, 47(2):263-29)) 1979.
Kalogiannis and Panageas. Zero-sum polymatrix markov games: Equilibrium collapse and efficient computation of nash equilibria, 2023. 16
S. Kannan, M. Kearns, J. Morgenstern, M. Pai, A. Roth, R. Vohra, and 7. S. Wu. Fairness incentives for myopic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 369-386, 2017. 1
M. Kearns and S. Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998. 9
S. Leonardos, G. Piliouras, and K. Spendlove. Exploration-exploitttion in multi-agent competition: Convergence with bounded rationality. In M. Ranzato. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26318 (8318-26331. Curran Associates, Inc., 2021. 3,4,1 17
R. Luce. Individual Choice Behavior: Theoretical analysis. Wiley, New York, NY, USA, 1959.
2, 3, 17
E. Mazumdar, L. J. Ratliff, and S. S. Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
R. McKelvey and T. Palfrey. experimental study of the centipede game. Econometrica, 60 (4):803-836, 1992. 17
R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995. 2, 3. 17
R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for extensive form games. Experimental economics, 1:9 41, 1998. 3, 17
J. McMahan, G. Artiglio, and Q Xie. Roping in uncertainty: Robustness and regularization in markov games. In Forty-first International Conference on Machine Learning, 2024. 6, 18, 20
P. Mertikopoulos and W. H. Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 1194):1297-1324, 2016. 3, 4, 17, 20
Mertikopoulos, C. Papadimitriou, and Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Anmual ACM-SIAM Symposium on Discrete Algorithms, page 2703-2717, USA, 2018. Society for Industrial and Applied Mathematics.
A.-H. Mohsenian-Rad V. W. Wong, J. Jatskevich, Schober, and A. Leon-Gareia. Autonomous demand-sidd management based on thee-rhhc energy consumption scheduling for the future smart grid. IEEE transactions on Smart Grid, 1(3):320 331, 2010.
Moon, F. Duncan, and Basar. Risk-sensitive zero-sum differential games. IEEE Transactions on Automatic Control, 64(4):1503-15118 2019. 17, 18
H. Moulin and J. P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3:2011221, 1978. 16
R. Munos, M. Valko, D. Calandriello, M. G. Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, C. Fiegel, A. Michi, M. Selvi, S. Girgin, N. Momchev, O. Bachem, D. Mankowitz, D. Precup, and B. Piot. Nash learning from human feedback. In Forty-first International Conference on Machine Learning, 2024.
Nash. Non-cooperative games. ANNALS OF MATHEMATICS, 54(2), 1951.
J. Nash. Non-cooperative games. Princeton University, 1950.
B. O'Neill. Nonmetric test of the minimax theory of two-person zerosum games. Proceedings of the National Academy of Sciences of the United States of America, 84(7):2106-210) 1987. 17
13

---

Published as a conference paper at ICLR 2025
R. Oprea and N. Robalino. Are humans more averse to aggregate risk? testing evolutionary economic theory. 2024. 5
K. Panaganti and D. Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference Artificial Intelligence and Statistics (AISTATS), pages 9582-9602, 2022. 17, 28
K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh. Robust reinforcement learning using offline data. Advances in Neural Information Processing Systems (NeurIPS), 2022. 17
W. Qiu, X. Wang, R. Yu, R. Wang, X. He, B. An, S. Obraztsova, and Z. Rabinovich. Rmix: Learning risk-sensitive policies for cooperative reinforcement learning agents. Advances in Neural Information Processing Systems, 34:23049-2306,, 2021. 17
J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Economet- rica, 33(3):520-535 1965. 20, 21
T. Roughgarden. Intrinsic robustness the price of anarchy. Journal of the ACM (JACM), 62(5): 1-42, 2015. 16
O. G. Selfridge. Adaptive strategies of learning study of two-person zero-sum competition. In Proceedings of the sixth international workshop on Machine learning, pages 412-415. Elsevier, 1989.
R. Selten and T. Chmura. Stationary concepts for experimental 2x2-games. American Economic Review, 98(3):938-966 2008. 3, 29, 30
L. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1055-1100, 1953.
S. Shen, C. Ma, Li, W. Liu, Fu, S. Mei, X. Liu, and C. Wang. Riskq: risk-sensitive multi-agent reinforcement learning value factorization. Advances Neural Information Processing Systems, (6:34791-34822 2023. 17
Y. Shen, W. Stannat, and K. Obermayer. Risk-sensitive markov control processes. SIAM Journal on Control and Optimization, (1aattionnn155)3333333 51(5::3652-3672 2013. 17
Y. Shen, M. J. Tobia, T. Sommer, and K. Obermayer. Risk-sensitive reinforcement learning. Neural computation, 26(7):1298-1322) 2014. 4, 8, 17, 18, 19
L. Shi, Li, Y. Wei, Y. Chen, M. Geist, and Y. Chi. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 2023. 28
L. Shi, E. Mazumdar, Y. Chi, and A. Wierman. Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. arXiv preprint 24t.::4004.88009 2024. 18
O. Slumbers, D. H. Mguni, S. B. Blumberg, M. Mcaleer, Y. Yang, and J. Wang. game- came-theoretic framework for managing risk in multi-agent systems. In International Conference on Machine Learning, pages 32059-33 32087. PMLR, 2023. 17
Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, Mitliagkas, N. Brown, and C. Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In The Eleventh International Conference on Learning Representations, 2023. 3, 4, 17, 20
Y. Sun, T. Liu, P. R. Kumar, and S. Shahrampour. Linear convergence of independent natural policy gradient in games with entropy regularization. IEEE Control Systems Letters, 8:1217-1222, 2024. 4
A. Tversky and D. Kahneman. Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and Uncertainty, 5:297-323, 1992. 2, 3,
M. Verma, S. Bhambri, and S. Kambhampati. On the brittle foundations of react prompting for agentic large language models. arXiv preprint arXiv:2405. /3966, 2024. 1
14

---

Published as a conference paper at ICLR 2025
Y. Viossat and A. Zapechelnyuk. No-regret dynamics and fictitious play. Journal of Economic Theory, 148(2):825-88)) 842, 2013. 2, 16
Z. Wang, Y. Shen, M. M. Zavlanos, and K. H. Johansson. Learning of nash equilibria in risk-averse games. arXiv preprint arXiv:2403. 2024. 17
M. Wellman and R. Wurman. Market-aware agents for multiagent world. Robotics and Autonomous Systems, 24(3-4):115--)
1998.
Z. Xu", K. Panaganti", and D. Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In Proceedings The 25th International Conference on Artificial Intelligence and Statistics. Conference Artificial Intelligence and Statisties, 2023. 17, 28
A. Yekkehkhany, T. Murray, and R. Nagi. Risk-averse equilibrium for games. arXiv preprini arXiv:2002.08414, 2020. 17
K. Zhang, T. Sun, Tao, S. Gene, S. Mallya, and T. Basar. Robust multi-agent reinforcement learning with model uncertainty. Advances in neural information processing systems, 33:10571-10583, 2020. 18
K. Zhang, Z. Yang, and T. Başar. Multi- ageett reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 202 la 1,
R. Zhang, Y. Hu, and N. Li. Soft robust MDPs and risk-sensitive MDPs: Equivalence, policy gradient, and sample complexity. In The Twelfth International Conference on Learning Representations, 2024. 17
S. Zhang, Liu, and S. Whiteson. Mean-variance policy iteration for risk-averse reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 10905-10913, 2021b.
15


Reviews:
[{"review_id": "gelwFc7LG9", "reviewer": "Reviewer_BGux", "summary": "Motivated by behavioral economics, this work proposes to investigate the combination of bounded rationality and risk aversion to define a regularized game leading to a new risk averse nash equilibrium concept. The main motivation of the paper is to introduce tractable equilibria in all n-player matrix and finite horizon Markov games. Notably, the introduced class of games is ‘tractable’ independently of the game structure while only depending on both levels of bounded rationality and risk aversion. The paper further proposes illustrations to motivate the games from the behavioral economics viewpoint and performs a few simulations to test the algorithms on simple examples. A sample complexity for finite Markov games under the generative model further completes the theoretical results.", "questions": "1. Could you please elaborate on how do you obtain figure 1? l. 69-71: ‘The markers … represent the necessary parameter values required to recreate the average strategy played by people in various 2-player games  in observational data…’\nCould you please clarify this?  How do you find the values of the bounded rationality and risk aversion levels (or their ratio) only looking at behavioral data? Are you saying that you test several such ratios, computing the equilibria that you define in the risk averse and bounded rationality game (which ones? There are not a priori unique?) and then the deployment of the obtained equilibrium policy cpincides with the ‘average strategy played by people’ (whatever that exactly means). As Fig. 1 plays an important role in motivating your approach (at least as a motivating illustration for the games you consider), I would expect a more rigorous and precise description here in order to strengthen the message and clarify to. \n\n2. Are both risk aversion formulations (2) and (3) related by Jensen’s inequality? Any implications? \n\n3. Where is continuity w.r.t. both arguments of D needed? Does this exclude the examples of D considered in this work? It seems to exclude the ones considered in the appendix (because of continuity w.r.t. second argument that is likely not needed). While I understand that the space limitation is constraining, I think examples should appear in the main part. \n\n4. Could you rather state your condition as $\\epsilon_1 \\epsilon_2 \\geq \\xi_1^* \\xi_2^*$ to include zero values of the parameters? This comes from your specific choice of $\\lambda$ that cancels one of the terms in your proof. Note that a symmetric choice for lambda is also possible (cancelling the other term). Otherwise the condition looks non-symmetric (I can set $\\epsilon_1 = 0$ but not $\\epsilon_2 = 0$, similarly for \\xi_1^*, \\xi_2^*) whereas the game is symmetric. Is positivity of all these parameters needed? Comments about the corner cases would be welcome here. \n\n5. More generally, it seems that one of the key argument in the proof of the main result (theorem 7) (if not the only key argument) is the joint convexity invoked. Under which condition do CCEs and NEs coincide more generally? How does your result fit with such known existing results. \n\n6. l. 373: You put a continuity assumption for matrix games (l. 207) and consider lower-semicontinuity in l. 373. Any specific reason for this discrepancy? Which ones of the examples you provide in table 1 satisfies continuity w.r.t. both arguments? \n\n7. Definition 7: Why is there a deviation w.r.t. the horizon step and not just $\\pi’_i, \\pi_{-i}$? Is this standard? If I set $\\epsilon_i = 0$ and remove the regularizers, do I recover the standard definition of NEs in finite horizon Markov games? \n\n8. Theorem 3: The condition you obtain for RAMG is not a generalization of the matrix games (two-player) one. Does this show some fundamental difference between the two player and multiplayer (\\geq 3) settings? \n\n9. Eq. 19 p. 17: If you exclude the action a_i of player i from being subject to \\rho_i, \\pi_{-i}, I guess you would get a less stringent assumption than what you currently have. Is this right? Essentially, excluding k=i in (31). \n\n10. Can you provide a proof of Corollary 7.1? \n\n11. Proof of Theorem 4: Do the examples you provide satisfy the L lipschitzness of D wrt the l_1 norm for the 2nd argument, the first one being fixed? \n\nMinor: \n- You cite Tversky and Kahneman (1992) in l. 154-155: ‘a preponderance of empirical evidence suggests that people do not play their Nash strategies …’ To the best of my knowledge, there is no single occurrence of the word ‘Nash equilibrium’ in this paper. The reference is relevant  though for the risk aversion discussion at least for single agents and beyond as a reference in behavioral economics. \n- \\sigma is introduced as a probability distribution over the product space P \\times \\bar{P}, then you also use it only for $\\pi$ s (l. 317), perhaps a slight abuse of notation here. \n- I think Theorem 6 p. 18 should appear in the main part to make existence very clear. You report an existence result in theorem 1 for RNEs but you do not state it for the equilibrium which are the focus of the work. I understand that space imitation might have been the issue, but I think this is important. Suggestion: In that case maybe defer Theorem 1 to the appendix and move Theorem 6 to the main part? \n- l. 392: ‘non-linear sum over’ is this a sum? The terminology is confusing here, is it rather a composition or a recursion? \n- Please be precise in the statement of Theorem 4, this is a high probability result, the result holds with probability at least 1-\\delta. \n- l. 452-453: the sentence needs to be revised, something missing.\n- l. 515 ‘and goal states for agents as well as goal states of agents’, meaning? \n- l. 518: ‘To introduce multi-agent effects’, what do you mean exactly by these effects? Collisions? Are they possible in your implementation? \n- l. 529: why would agent 1 wait? Does agent 2 make it riskier for agent 1 to move if they move together? Can you explain? \n- l. 988: what do you mean by a strictly competitive game? \n- p. 21, l. 1132- …: The 1/2 does not seem to be useful in the proof. \n- p. 29: ‘to arrive at the CCE \\sigma of the four player game’, is there a unique one?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Writing is clear overall (I have some concerns for some aspects though, see next section) and the paper is well-organized. The proofs are well exposed in the appendix. \n- Investigating the tractability of games combining bounded rationality and risk aversion is interesting. In particular I find the idea of achieving tractability independently from the payoffs interesting. \n- The paper covers matrix games and their extension to finite horizon Markov games. More importantly the results hold for general sum games.  \n- Modelling the behavior of decision making agents and their strategic interaction beyond expected utility theory is interesting on its own.", "weaknesses": "- My main concern about this paper is the following question: What exactly makes the introduced games tractable? The paper argues that it is the combination of bounded rationality and risk aversion. I find the focus on tractability rather confusing. \nRisk aversion has its own motivation but it is unclear if it is required here for tractability. To be precise, I think the contribution in this paper is that you can achieve tractability (for computing another solution concept  than NE/CCE relating to a modified game) independently of the knowledge of payoff functions (their bounds I guess). More precisely, I think bounded rationality is already enough to allow for tractability but it should require some assumptions on the payoffs which this paper avoids. Please correct me if I have missed something here. The paper does not exactly present the contribution this way. In particular, I think the following statements would gain in clarity: \n\n-- l. 111-112: ‘RQE not only incorporates features of human decision-making but are also more amenable to computation than QRE …’ Why? There is no extended discussion about this whereas I believe it is essential to clarify the contributions. \n\n-- l. 235-238: While risk aversion might not be enough, I think bounded rationality should be enough (e.g. QRE as demonstrated in a number of works) under relevant assumptions on the structure of the game (mainly conditions on the bounded rationality level compared to the magnitude of the utilities/rewards). I find the presentation order confusing here. You start by introducing risk aversion and show its shortcomings as for the tractability of computing equilibria in such risk averse games to motivate the need of something else but equilibria should become tractable only with bounded rationality. \n\n-- From the title and the abstract (and throughout the paper), the emphasis is on tractability, as if both are actually needed to ‘achieve’ tractability. If this is not the case as bounded rationality is the main enabler, I would maybe highlight less this computational aspect and clarify that the combination brings you the possibility to achieve tractability under a condition on both levels of bounded rationality and risk aversion which is independent of the rewards. How does this condition compare to the one for say QREs? What’s the price to pay and advantages (if any) for RQNEs compared to QREs (beyond the advantage of incorporating risk aversion)? \n\n- Equilibrium collapse is briefly mentioned in l. 294. I would like to see a more in-depth description of how the results of this paper connect to the prior work regarding this phenomenon. It seems that the extended game you introduce seems to have some zero sum structure under a perhaps more stringent assumption than what you set (\\epsilon_1 = \\xi_{2,1} and \\epsilon_2 = \\xi_{1,2}, a condition satisfying your condition), under which J_1 + J_2 + \\bar{J}_1 + \\bar{J}_2 = 0. This can be seen from setting \\lambda = 1/2 in your proof of Theorem 7 p. 21, l. 1133-1146. Is this an observation that connects to prior work about zero sum games and equilibrium collapse? It is also worth mentioning that setting \\lambda = 1/2 leads to a condition that is consistent with your extension to the n-player setting (l. 1226-1232). \n\n- I think the introduction and motivation of (6) and (7) needs some improvement. Could you give more motivation and intuition? \n\n- The notations $\\xi_1^*, \\xi_2^*$ are quite confusing, especially that you also use the notations $\\tau_1, \\tau_2$ in Fig. 1 without defining them in the main part. What do you mean precisely by $\\tau_1, \\tau_2$ satisfy the conditions of Theorem 2 (l. 328)? How do the \\tau s and \\xi s relate?I believe one issue in the presentation is that you chose to hide \\tau in the definition of the regularizer D without putting it in front of D (as it appears from the appendix). Maybe a solution is just to add the examples to the main part to clarify this and further comment on the relationship between the \\xi s and \\tau s. \n\n- Comments about experiments: While the paper focuses on RQREs, experiments do not seem to illustrate the concept. What are the RQREs in this game and why? Are they different from NEs? Why would they be more reasonable? \n\n- The introduction (and some other parts of the work e.g. l. 772-780), highlights the limitations of CCEs. Then Theorem 2 assumes access to a CCE of the 4-player game (which can be computed with a no-regret algorithm). While this CCE is for the modified (regularized) game and not the original one, why would this alleviate all the limitations that are inherent to CCEs in general and that you highlight in the paper? More specifically, the facts that the set of CCEs can be large, may have support on strictly dominated strategies and that stationary CCEs are PPAD-hard to compute in dynamic general sum games (l. 47-51). For the last point, does it mean that your output is also a nonstationary CCE since you also rely on no-regret algorithms (l. 8 of algorithm 1).   \n \n- Dependence on the action space size: a host of theoretical results in the MARL literature have devoted efforts to ‘break’ the ‘curse of multi-agency’ and go from the product of action spaces to the sum. Your sample complexity is exponential in the number of players. While I understand that space might have been constraining, at least a comment is needed here on the theorem. The very last point of the conclusion mentions scalability but this is not clearly delineating the limitations of the result and why. \n\n- I have several other questions that I would like the authors to address for clarifying their contributions and the technical novelty.\n\nMinor:\n- l. 47-48: ‘the set of CCE can be large (introducing an additional problem of equilibrium selection)’: This equilibrium solution problem is already largely relevant for Nash equilibria, I find the argument confusing here. This is even more confusing since you also rely on CCE computation (for a modified game though) in the paper. \n- l. 305-307: H notations do not seem to be used in the main part. \n- l. 377, eq. (9): \\tilde P V: the notation is a bit confusing here, I guess it is the usual dynamic programming notation but \\tilde{P} \\in \\Delta_S and V \\in R^S is a bit unclear, \\tilde{P} is usually a matrix. \n- (24) l. 1045: for the argmax to be unique I guess you need D_i to be strictly convex w.r.t. p_i here. \n- Proposition 1 p. 20: bounded rationality does not seem to play any role in obtaining this result, this is probably worth mentioning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iw7tTGbB6B", "reviewer": "Reviewer_GTtm", "summary": "The paper investigates incorporating risk aversion and bounded rationality in order to tractably compute risk-averse quantal response equilibria (RQE) for n-player matrix and finite-horizon Markov games. The paper proposes computing the RQE is advantageous because it is tractable under certain conditions independent of the game structure and it models human behavior better. The conditions for tractability of RQE is stated with respect to degree of risk aversion and degree of bounded rationality. The connection between using no-regret learning algorithms and computing the coarse correlated equilibrium (CCE) of the 2n-player game and computing the RQE of the n-player game is provided. The method and the definitions are extended to Markov games and the experiment results on a toy Cliff Walk grid-world game is given which support the claims of the paper.", "questions": "* What is the significance of the choice of aggregate risk aversion and action-dependent risk aversion? When should we pick either one?\n* Is there any advantage of converging to the RQE rather than optimizing to the optimal solutions, since the policies are to be used by artificial agents and the purpose is not to model human behavior? Is it only to be used because it is more tractable or do you foresee another significant use for it due to risk aversion and bounded rationality modeling?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Novel contribution while bringing a theoretically grounded view on risk aversion and bounded rationality to Markov games which can eventually be applied to more complex MARL scenarios. Adjusting the games so that RQE is achieved tractably by no-regret learning and having the tractability not depend on the underlying game structure is useful.\n* Claims are supported extensively by proofs.\n* The experiment on Cliff Walk demonstrates the risk averseness well.\n* Paper is well written in general.", "weaknesses": "* There is only one example game for Markov game results and it is very toy.\n* Bounded rationality is less obvious than risk averseness on Cliff Walk experiments. Interpreting bounded rationality from the experiments is difficult.\n* Paper has some minor typos (example line 160).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "igAZhrJs3B", "reviewer": "Reviewer_E3pZ", "summary": "This paper discusses multi-agent learning in a setting where the agents are risk-averse. By introducing risk aversion and quantal response into the agents' behaviour, the authors simplify computations to achieve a risk-averse quantal response equilibrium (RQE). This is accomplished via some clever tooling, applying a dual representation from [1] to convert the problem into a convex optimization problem under certain values of risk aversion. The trade-off is that it introduces n additional players into the game. The theory from the repeated game setting is then extended to the Markov game setting, where it establishes equivalence to the repeated game setting, quantifies the learning error, and implies convergence to RQE under specific parameter settings. A toy example is presented to convince the reader that the technology is functional.\n\n[1] Föllmer, Hans, and Alexander Schied. \"Convex measures of risk and trading constraints.\" Finance and stochastics 6 (2002): 429-447.", "questions": "- Could we not also have a baseline comparison with standard algorithms, such as Nash Q-learning in the MG, or other MARL algorithms (e.g., multi-agent PPO), to assess its performance against established algorithms?\n- Similarly, could we extend the MG setting to more than two players in the toy examples? This could significantly increase computation time, even with the proposed, more efficient, algorithm.\n- How would this accommodate non-convex compositions of risk-averse functions? Is there a simple extension, or would it be more complex?\n- What economic scenarios could the RAMG apply to, given that the concept of risk aversion originally stems from economics?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors perform a rigorous analysis and provide convincing arguments for a well-defined system.\n- The work could have real economic applications.\n- There is good novelty in applying the dual formulation of [1] to this multi-agent setting and constructing the loss functions in Eq. (6) and (7).", "weaknesses": "- The notation could be a bit confusing at times; the difference between $\\pi$ and $p_i$ is not clearly defined and can be hard for the reader to follow.\n- Typo in line 160: \"we make u a general class...\"\n- The experiments lack breadth in demonstrating the algorithm’s efficacy across diverse problem settings. Only one cliff walk example is demonstrated, and very standard simple benchmarks are used for the repeated game.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tgHTSJBvfv", "reviewer": "Reviewer_JYbT", "summary": "The authors propose an algorithm for multi-agent game and reinforcement learning inspired by behavioral economics, with risk aversion and bounded rationality. They study a new class of equilibria called risk-averse quantal response equilibria (RQE), which is computationally tractable and with more human characteristics. Moreover, it provides an analysis of sample complexity for computing RQE in finite-horizon Markov games using generative models\n\nEspecially, these equilibria are independent of specific game structures and instead hinge on the degree of agents' risk aversion and bounded rationality. The authors also validate the effectiveness of RQE by showing its alignment with human behavior in experimental game studies.", "questions": "- Typo on L161: To allow agents to have risk preferences we make u a general class of convex\n- What challenges arise in adopting conditions weaker than requiring a simulator?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The authors introduces games with risk-averse agents and bounded rationality, allowing for the computation of risk-averse quantal response equilibrium (RQE), which is realistic and computationally feasible.\n- RQE can be computed in polynomial time in all $n$-player matrix games under specific risk aversion and bounded rationality conditions, irrespective of the underlying payoffs.\n- The authors present a sampling-based algorithm with finite-sample guarantees for learning approximate RQE in unknown environments.", "weaknesses": "- While the paper applies duality and risk aversion concepts, these techniques have been previously explored in the context of game theory and multi-agent reinforcement learning, raising questions about the technical novelty of the contributions.\n- Extending the findings to finite-horizon Markov Decision Processes (MDPs) may be somewhat straightforward, as the process involves relatively conventional methods. While this extension adds scope, it may not significantly deepen the theoretical insights or complexity of the approach.\n- The proposed algorithm requires access to a simulator, which is a strong assumption and may limit the practical applicability of the method, especially in real-world scenarios where such simulators are unavailable or costly to obtain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)